C# 检查数字是否为质数

Check if number is prime number

提问by user1954418

I would just like to ask if this is a correct way of checking if number is prime or not? because I read that 0 and 1 are NOT a prime number.

我想问一下，这是否是检查数字是否为素数的正确方法？因为我读到 0 和 1 不是素数。

int num1;

Console.WriteLine("Accept number:");
num1 = Convert.ToInt32(Console.ReadLine());
if (num1 == 0 || num1 == 1)
{
    Console.WriteLine(num1 + " is not prime number");
    Console.ReadLine();
}
else
{
    for (int a = 2; a <= num1 / 2; a++)
    {
        if (num1 % a == 0)
        {
            Console.WriteLine(num1 + " is not prime number");
            return;
        }

    }
    Console.WriteLine(num1 + " is a prime number");
    Console.ReadLine();
}

回答by Mike Perrenoud

Here's a good example. I'm dropping the code in here just in case the site goes down one day.

这是一个很好的例子。我把代码放在这里以防万一网站有一天宕机。

using System;

class Program
{
    static void Main()
    {
    //
    // Write prime numbers between 0 and 100.
    //
    Console.WriteLine("--- Primes between 0 and 100 ---");
    for (int i = 0; i < 100; i++)
    {
        bool prime = PrimeTool.IsPrime(i);
        if (prime)
        {
        Console.Write("Prime: ");
        Console.WriteLine(i);
        }
    }
    //
    // Write prime numbers between 10000 and 10100
    //
    Console.WriteLine("--- Primes between 10000 and 10100 ---");
    for (int i = 10000; i < 10100; i++)
    {
        if (PrimeTool.IsPrime(i))
        {
        Console.Write("Prime: ");
        Console.WriteLine(i);
        }
    }
    }
}

Here is the class that contains the IsPrimemethod:

这是包含该IsPrime方法的类：

using System;

public static class PrimeTool
{
    public static bool IsPrime(int candidate)
    {
    // Test whether the parameter is a prime number.
    if ((candidate & 1) == 0)
    {
        if (candidate == 2)
        {
        return true;
        }
        else
        {
        return false;
        }
    }
    // Note:
    // ... This version was changed to test the square.
    // ... Original version tested against the square root.
    // ... Also we exclude 1 at the end.
    for (int i = 3; (i * i) <= candidate; i += 2)
    {
        if ((candidate % i) == 0)
        {
        return false;
        }
    }
    return candidate != 1;
    }
}

回答by Soner G?nül

var number;

Console.WriteLine("Accept number:");
number = Convert.ToInt32(Console.ReadLine());
if(IsPrime(number))
{
  Console.WriteLine("It is prime");
}
else
{
  Console.WriteLine("It is not prime");
}       

public static bool IsPrime(int number)
{
    if (number <= 1) return false;
    if (number == 2) return true;
    if (number % 2 == 0) return false;

    var boundary = (int)Math.Floor(Math.Sqrt(number));

    for (int i = 3; i <= boundary; i+=2)
        if (number % i == 0)
            return false;

    return true;        
}

I changed number / 2to Math.Sqrt(number)because from in wikipedia, they said:

我换number / 2到Math.Sqrt(number)，因为在维基百科，他们说：

This routine consists of dividing nby each integer mthat is greater than 1 and less than or equal to the square root of n. If the result of any of these divisions is an integer, then nis not a prime, otherwise it is a prime. Indeed, if n = a*bis composite (with a and b ≠ 1) then one of the factors aor bis necessarily at most square root of n

该例程包括将n除以每个大于 1 且小于或等于n 的平方根的整数m。如果这些除法中的任何一个的结果是整数，则n不是素数，否则为素数。实际上，如果n = a*b是合数（a 和 b ≠ 1），那么因子a或b 之一必然至多是 n 的平方根

回答by 0x90

Using Soner's routine, but with a slight variation: we will run until iequals Math.Ceiling(Math.Sqrt(number))that is the trick for the naive solution:

使用 Soner 的例程，但略有变化：我们将运行直到i等于Math.Ceiling(Math.Sqrt(number))这是天真的解决方案的技巧：

boolean isPrime(int number)
{

    if (number == 1) return false;
    if (number == 2) return true;

    var limit = Math.Ceiling(Math.Sqrt(number)); //hoisting the loop limit

    for (int i = 2; i <= limit; ++i)  {
       if (number % i == 0)  return false;
    }

    return true;

}

回答by Panos Theof

Based on @Micheal's answer, but checks for negative numbers and computes the square incrementally

基于@Micheal 的回答，但会检查负数并逐步计算平方

    public static bool IsPrime( int candidate ) {
        if ( candidate % 2 <= 0 ) {
            return candidate == 2;
        }
        int power2 = 9;
        for ( int divisor = 3; power2 <= candidate; divisor += 2 ) {
            if ( candidate % divisor == 0 )
                return false;
            power2 += divisor * 4 + 4;
        }
        return true;
    }

回答by Raz Megrelidze

Here's a nice way of doing that.

这是一个很好的方法。

    static bool IsPrime(int n)
    {
        if (n > 1)
        {
            return Enumerable.Range(1, n).Where(x => n%x == 0)
                             .SequenceEqual(new[] {1, n});
        }

        return false;
    }

And a quick way of writing your program will be:

编写程序的一种快速方法是：

        for (;;)
        {
            Console.Write("Accept number: ");
            int n = int.Parse(Console.ReadLine());
            if (IsPrime(n))
            {
                Console.WriteLine("{0} is a prime number",n);
            }
            else
            {
                Console.WriteLine("{0} is not a prime number",n);
            }
        }

回答by user2771704

Find this example in one book, and think it's quite elegant solution.

在一本书中找到这个例子，并认为这是一个非常优雅的解决方案。

 static void Main(string[] args)
    {
        Console.Write("Enter a number: ");
        int theNum = int.Parse(Console.ReadLine());

        if (theNum < 3)  // special case check, less than 3
        {
            if (theNum == 2)
            {
                // The only positive number that is a prime
                Console.WriteLine("{0} is a prime!", theNum);
            }
            else
            {
                // All others, including 1 and all negative numbers, 
                // are not primes
                Console.WriteLine("{0} is not a prime", theNum);
            }
        }
        else
        {
            if (theNum % 2 == 0)
            {
                // Is the number even?  If yes it cannot be a prime
                Console.WriteLine("{0} is not a prime", theNum);
            }
            else
            {
                // If number is odd, it could be a prime
                int div;

                // This loop starts and 3 and does a modulo operation on all
                // numbers.  As soon as there is no remainder, the loop stops.
                // This can be true under only two circumstances:  The value of
                // div becomes equal to theNum, or theNum is divided evenly by 
                // another value.
                for (div = 3; theNum % div != 0; div += 2)
                    ;  // do nothing

                if (div == theNum)
                {
                    // if theNum and div are equal it must be a prime
                    Console.WriteLine("{0} is a prime!", theNum);
                }
                else
                {
                    // some other number divided evenly into theNum, and it is not
                    // itself, so it is not a prime
                    Console.WriteLine("{0} is not a prime", theNum);
                }
            }
        }

        Console.ReadLine();
    }

回答by variable

   bool flag = false;


            for (int n = 1;n < 101;n++)
            {
                if (n == 1 || n == 2)
                {
                    Console.WriteLine("prime");
                }

                else
                {
                    for (int i = 2; i < n; i++)
                    {
                        if (n % i == 0)
                        {
                            flag = true;
                            break;
                        }
                    }
                }

                if (flag)
                {
                    Console.WriteLine(n+" not prime");
                }
                else
                {
                    Console.WriteLine(n + " prime");
                }
                 flag = false;
            }

            Console.ReadLine();

回答by Tomas

Only one row code:

只有一行代码：

    private static bool primeNumberTest(int i)
    {
        return i > 3 ? ( (Enumerable.Range(2, (i / 2) + 1).Where(x => (i % x == 0))).Count() > 0 ? false : true ) : i == 2 || i == 3 ? true : false;
    }

回答by Alexandru

I've implemented a different method to check for primes because:

我已经实现了一种不同的方法来检查素数，因为：

• Most of these solutions keep iterating through the same multiple unnecessarily (for example, they check 5, 10, and then 15, something that a single % by 5 will test for).
• A % by 2 will handle all even numbers (all integers ending in 0, 2, 4, 6, or 8).
• A % by 5 will handle all multiples of 5 (all integers ending in 5).
• What's left is to test for even divisions by integers ending in 1, 3, 7, or 9. But the beauty is that we can increment by 10 at a time, instead of going up by 2, and I will demonstrate a solution that is threaded out.
• The other algorithms are not threaded out, so they don't take advantage of your cores as much as I would have hoped.
• I also needed support for really large primes, so I needed to use the BigInteger data-type instead of int, long, etc.

• 这些解决方案中的大多数都会不必要地迭代相同的多个（例如，它们检查 5、10 和 15，单个 % by 5 将测试的东西）。
• A % by 2 将处理所有偶数（所有以 0、2、4、6 或 8 结尾的整数）。
• A % by 5 将处理所有 5 的倍数（所有以 5 结尾的整数）。
• 剩下的就是测试以 1、3、7 或 9 结尾的整数的偶数除法。但美妙的是我们可以一次增加 10，而不是增加 2，我将演示一个解决方案穿出。
• 其他算法没有线程化，因此它们不会像我希望的那样充分利用您的内核。
• 我还需要支持非常大的素数，所以我需要使用 BigInteger 数据类型而不是 int、long 等。

Here is my implementation:

这是我的实现：

public static BigInteger IntegerSquareRoot(BigInteger value)
{
    if (value > 0)
    {
        int bitLength = value.ToByteArray().Length * 8;
        BigInteger root = BigInteger.One << (bitLength / 2);
        while (!IsSquareRoot(value, root))
        {
            root += value / root;
            root /= 2;
        }
        return root;
    }
    else return 0;
}

private static Boolean IsSquareRoot(BigInteger n, BigInteger root)
{
    BigInteger lowerBound = root * root;
    BigInteger upperBound = (root + 1) * (root + 1);
    return (n >= lowerBound && n < upperBound);
}

static bool IsPrime(BigInteger value)
{
    Console.WriteLine("Checking if {0} is a prime number.", value);
    if (value < 3)
    {
        if (value == 2)
        {
            Console.WriteLine("{0} is a prime number.", value);
            return true;
        }
        else
        {
            Console.WriteLine("{0} is not a prime number because it is below 2.", value);
            return false;
        }
    }
    else
    {
        if (value % 2 == 0)
        {
            Console.WriteLine("{0} is not a prime number because it is divisible by 2.", value);
            return false;
        }
        else if (value == 5)
        {
            Console.WriteLine("{0} is a prime number.", value);
            return true;
        }
        else if (value % 5 == 0)
        {
            Console.WriteLine("{0} is not a prime number because it is divisible by 5.", value);
            return false;
        }
        else
        {
            // The only way this number is a prime number at this point is if it is divisible by numbers ending with 1, 3, 7, and 9.
            AutoResetEvent success = new AutoResetEvent(false);
            AutoResetEvent failure = new AutoResetEvent(false);
            AutoResetEvent onesSucceeded = new AutoResetEvent(false);
            AutoResetEvent threesSucceeded = new AutoResetEvent(false);
            AutoResetEvent sevensSucceeded = new AutoResetEvent(false);
            AutoResetEvent ninesSucceeded = new AutoResetEvent(false);
            BigInteger squareRootedValue = IntegerSquareRoot(value);
            Thread ones = new Thread(() =>
            {
                for (BigInteger i = 11; i <= squareRootedValue; i += 10)
                {
                    if (value % i == 0)
                    {
                        Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i);
                        failure.Set();
                    }
                }
                onesSucceeded.Set();
            });
            ones.Start();
            Thread threes = new Thread(() =>
            {
                for (BigInteger i = 3; i <= squareRootedValue; i += 10)
                {
                    if (value % i == 0)
                    {
                        Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i);
                        failure.Set();
                    }
                }
                threesSucceeded.Set();
            });
            threes.Start();
            Thread sevens = new Thread(() =>
            {
                for (BigInteger i = 7; i <= squareRootedValue; i += 10)
                {
                    if (value % i == 0)
                    {
                        Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i);
                        failure.Set();
                    }
                }
                sevensSucceeded.Set();
            });
            sevens.Start();
            Thread nines = new Thread(() =>
            {
                for (BigInteger i = 9; i <= squareRootedValue; i += 10)
                {
                    if (value % i == 0)
                    {
                        Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i);
                        failure.Set();
                    }
                }
                ninesSucceeded.Set();
            });
            nines.Start();
            Thread successWaiter = new Thread(() =>
            {
                AutoResetEvent.WaitAll(new WaitHandle[] { onesSucceeded, threesSucceeded, sevensSucceeded, ninesSucceeded });
                success.Set();
            });
            successWaiter.Start();
            int result = AutoResetEvent.WaitAny(new WaitHandle[] { success, failure });
            try
            {
                successWaiter.Abort();
            }
            catch { }
            try
            {
                ones.Abort();
            }
            catch { }
            try
            {
                threes.Abort();
            }
            catch { }
            try
            {
                sevens.Abort();
            }
            catch { }
            try
            {
                nines.Abort();
            }
            catch { }
            if (result == 1)
            {
                return false;
            }
            else
            {
                Console.WriteLine("{0} is a prime number.", value);
                return true;
            }
        }
    }
}

Update: If you want to implement a solution with trial division more rapidly, you might consider having a cache of prime numbers. A number is only prime if it is not divisible by other prime numbers that are up to the value of its square root. Other than that, you might consider using the probabilistic version of the Miller-Rabin primality testto check for a number's primality if you are dealing with large enough values (taken from Rosetta Code in case the site ever goes down):

更新：如果您想更快地实施带有试除法的解决方案，您可以考虑使用质数缓存。一个数只有在不能被其他达到其平方根值的素数整除时才是素数。除此之外，如果您正在处理足够大的值（从 Rosetta Code 获取，以防网站出现故障），您可以考虑使用Miller-Rabin 素数测试的概率版本来检查数字的素数：

// Miller-Rabin primality test as an extension method on the BigInteger type.
// Based on the Ruby implementation on this page.
public static class BigIntegerExtensions
{
  public static bool IsProbablePrime(this BigInteger source, int certainty)
  {
    if(source == 2 || source == 3)
      return true;
    if(source < 2 || source % 2 == 0)
      return false;

    BigInteger d = source - 1;
    int s = 0;

    while(d % 2 == 0)
    {
      d /= 2;
      s += 1;
    }

    // There is no built-in method for generating random BigInteger values.
    // Instead, random BigIntegers are constructed from randomly generated
    // byte arrays of the same length as the source.
    RandomNumberGenerator rng = RandomNumberGenerator.Create();
    byte[] bytes = new byte[source.ToByteArray().LongLength];
    BigInteger a;

    for(int i = 0; i < certainty; i++)
    {
      do
      {
        // This may raise an exception in Mono 2.10.8 and earlier.
        // http://bugzilla.xamarin.com/show_bug.cgi?id=2761
        rng.GetBytes(bytes);
        a = new BigInteger(bytes);
      }
      while(a < 2 || a >= source - 2);

      BigInteger x = BigInteger.ModPow(a, d, source);
      if(x == 1 || x == source - 1)
        continue;

      for(int r = 1; r < s; r++)
      {
        x = BigInteger.ModPow(x, 2, source);
        if(x == 1)
          return false;
        if(x == source - 1)
          break;
      }

      if(x != source - 1)
        return false;
    }

    return true;
  }
}

回答by Waqar

You can also find range of prime numbers till the given number by user.

您还可以找到素数的范围，直到用户给定的数字。

CODE:

代码：

class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Input a number to find Prime numbers\n");
            int inp = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("\n Prime Numbers are:\n------------------------------");
            int count = 0;

            for (int i = 1; i <= inp; i++)
            {
                for (int j = 2; j < i; j++) // j=2 because if we divide any number with 1 the remaider will always 0, so skip this step to minimize time duration.
                {
                    if (i % j != 0)
                    {
                        count += 1;
                    }
                }
                if (count == (i - 2))
                    {
                        Console.Write(i + "\t"); 
                    }

                count = 0;
            }

            Console.ReadKey();

        }
    }