找到给定数字的所有素数的最佳,最高效的算法是什么？

Question

我现在有这个方法工作正常:

 private static List<long> GetPrimeNumbers(long number)
        {
            var result = new List<long>();
            for (var i = 0; i <= number; i++)
            {
                var isPrime = true;
                for (var j = 2; j < i; j++) 
                {
                    if (i % j == 0) 
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                {
                    result.Add(i);
                }
            }
            return result;
        }

以上是最好的算法吗？

当数字超过100000时,它真的很慢.

我的意思是,找到小于或等于给定数字的素数的最佳,最高效的算法是什么？

Answer 1

1. Eratosthenes的筛子.该算法可以生成最多的所有素数n.时间复杂度 - O(nlog(n)),内存复杂性 -O(n)

2. BPSW素性测试.该算法可以检查是否n为pseudoprime.它在前10 ^ 15个数字上进行了测试.时间复杂性 - O(log(n)).

更新: 我做了一些研究并编写了在c#中生成素数的简单实现.当我们检查数字N的素数时的主要想法- 我们只需要检查它是否可被任何小于的素数整除sqrt(N).

首次实施:

public static List<int> GeneratePrimes(int n)
{
  var primes = new List<int>();
  for(var i = 2; i <= n; i++)
  {
    var ok = true;
    foreach(var prime in primes)
    {
      if (prime * prime > i)
        break;
      if (i % prime == 0)
      {
        ok = false;
        break;
      }
    }
    if(ok)
      primes.Add(i);
  }
  return primes;
}

测试结果:

10^6 - 0.297s
10^7 - 6.202s
10^8 - 141.860s

使用第二个执行并行计算:1.生成所有素数达sqrt(N) 2.生成所有素数sqrt(N) + 1来N使用素数最多sqrt(N)使用并行计算.

public static List<int> GeneratePrimesParallel(int n)
    {
      var sqrt = (int) Math.Sqrt(n);
      var lowestPrimes = GeneratePrimes(sqrt);
      var highestPrimes =  (Enumerable.Range(sqrt + 1, n - sqrt)
                                .AsParallel()
                                .Where(i => lowestPrimes.All(prime => i % prime != 0)));
      return lowestPrimes.Concat(highestPrimes).ToList();
    }

测试结果:

10^6 - 0.276s
10^7 - 4.082s
10^8 - 78.624