检查号码是否为素数

Question

我想问一下这是否是检查数字是否为素数的正确方法？因为我读到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();
}

Answer 1

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;        
}

我改为number / 2,Math.Sqrt(number)因为在维基百科,他们说:

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

Answer 2

使用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;

}

Answer 3

这是一个很好的方法.

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

        return false;
    }

编写程序的快速方法是:

        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);
            }
        }

Answer 4

这基本上是 Eric Lippert 在上面某处提出的绝妙建议的实现。

    public static bool isPrime(int number)
    {
        if (number == 1) return false;
        if (number == 2 || number == 3 || number == 5) return true;
        if (number % 2 == 0 || number % 3 == 0 || number % 5 == 0) return false;

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

        // You can do less work by observing that at this point, all primes 
        // other than 2 and 3 leave a remainder of either 1 or 5 when divided by 6. 
        // The other possible remainders have been taken care of.
        int i = 6; // start from 6, since others below have been handled.
        while (i <= boundary)
        {
            if (number % (i + 1) == 0 || number % (i + 5) == 0)
                return false;

            i += 6;
        }

        return true;
    }

Answer 5

这是一个很好的例子.我正在放弃这里的代码,以防万一网站出现故障.

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);
        }
    }
    }
}

这是包含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;
    }
}

Answer 6

我已经实现了一种不同的方法来检查质数,因为:

• 大多数这些解决方案不必要地迭代通过相同的倍数(例如,他们检查5,10和15,单个%乘5将测试).
• %乘2将处理所有偶数(所有整数以0,2,4,6或8结尾).
• A乘以5将处理5的所有倍数(以5结尾的所有整数).
• 剩下的是通过以1,3,7或9结尾的整数来测试偶数除法.但美妙的是我们可以一次增加10,而不是上升2,我将演示一个解决方案,即线程化.
• 其他算法没有线程化,所以他们没有像我希望的那样利用你的核心.
• 我还需要支持真正的大质数,所以我需要使用BigInteger数据类型而不是int,long等.

这是我的实现:

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;
            }
        }
    }
}

更新:如果您想更快地实现试验分区的解决方案,您可能会考虑使用素数缓存.如果数字不能被其平方根值达到的其他素数整除,则该数字仅为素数.除此之外,您可以考虑使用Miller-Rabin素数测试的概率版本来检查数字的素数,如果您处理足够大的值(如果站点出现故障则从Rosetta Code中获取):

// 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;
  }
}