检查C#中的数字是否为素数

Question

下面的代码可以工作，但是对于某些数字，它需要大量的时间来判断这个数字是否是素数。我能怎么做才能让它更快？以下是代码：

using System;
using System.Collections.Generic;
using System.Linq;``
using System.Text;
using System.Threading.Tasks;

namespace Exercise23
{
    class Exercise23
    {
        static void Main(string[] args)
        {
            long number = long.Parse(Console.ReadLine());
            if (IsPrime(number))
            {
                Console.WriteLine("True");
            }
            else
            {
                Console.WriteLine("False");
            }
        }
        public static bool IsPrime(long number)
        {
            if (number == 1) return false;
            if (number == 2) return true;
            //if (number == 6737626471) return true;

            if (number % 2 == 0) return false;    

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

Answer 1

最简单的改进是缩短循环时间。如果数字不是素数，它可以写成

  N = A * B 

让A <= B；在最坏的情况下(A == B)和A <= sqrt(N)。

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

    long N = (long) (Math.Sqrt(number) + 0.5);

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

    return true;
  }

所以你有O(sqrt(N))算法而不是O(N)算法。有关真正的改进(关于大型number)，请参见

AKS测试(主要是学术用途)

test

Rabin-Miller测试

test

Answer 2

基于这个答案：https://stackoverflow.com/a/26760082/4499267可以是一种加快速度的方法：

• 该算法可以通过观察到所有素数都是6k±1形式(2和3除外)而得到进一步的改进。
• 这是因为对于某些整数k和i=−1，0，1，2，3或4，2除以(6k + 0)，(6k + 2)，(6k +4)和3除(6k + 3)，所有整数都可以表示为(6k + i)。
• 因此，更有效的方法是检验n是否可以被2或3整除，然后检查6k±1≤√n的所有数目。
• 这是测试所有m到√n的速度的3倍。

这里有一个C实现

int IsPrime(unsigned int number) {
    if (number <= 3 && number > 1) 
        return 1;            // as 2 and 3 are prime
    else if (number == 1 || number%2==0 || number%3==0) 
        return 0;     // check if number is divisible by 2 or 3
    else {
        unsigned int i;
        for (i=5; i*i<=number; i+=6) {
            if (number % i == 0 || number%(i + 2) == 0) 
                return 0;
        }
        return 1; 
    }
}