找到给定数以内的所有质数的最佳、最高效的算法是什么?
本文关键字：最佳 高效 算法 是什么 | 更新日期: 2023-09-27 18:13:06
我目前有这个方法工作得很好:
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时，它真的很慢。
我的意思是，找到小于或等于给定数字的质数的最佳，最高效的算法是什么?
-
埃拉托色尼筛。该算法可以生成到
n的所有素数。时间复杂度-O(nlog(n))，内存复杂度-O(n) -
BPSW素数检验。该算法可以检测
n是否为伪素数。它在前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
也许阿特金筛子是性能最好的，尽管据我所知，后来有人找到了更好的筛子。
Erathosthenes和Sundaram也有他们自己的筛子，这更容易实现。它们中的任何一个都可以通过分别在每个数字中寻找一个因子直到极限来踢出填充。
所有筛比一次分解一个值使用更多的工作内存，但通常仍然比得到的质数列表占用更少的内存。
你可以大大改进你的算法测试n是否是2和sqrt(n)之间的任何整数的倍数。
private static List<int> GetPrimeNumbers2(long number)
{
var result = new List<int>();
for (var i = 0; i <= number; i++)
{
var isPrime = true;
var n = Math.Floor(Math.Sqrt(i));
for (var j = 2; j <= n; j++)
{
if (i % j == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
result.Add(i);
}
}
return result;
}
这将复杂度从O(NN)变为O(Nsqrt(N))。
已知测试一般数素数的最快算法是椭圆曲线素数证明(Elliptic Curve primality Proving, ECPP): http://en.wikipedia.org/wiki/Elliptic_curve_primality_proving我想实现它会很困难，所以只有在你真的需要的时候才这么做。这里可能有一些图书馆可以帮助你。
这将为初始执行提供合理的性能，然后为任何重复请求提供接近O(1)的性能(它将是O(N)，但非常非常小)，并且对于大于当前所见最大值的值提供合理的性能。
private static List<ulong> KnownPrimes = new List<ulong>();
private static ulong LargestValue = 1UL;
private static List<ulong> GetFastestPrimeNumbers(ulong number)
{
var result = new List<ulong>();
lock (KnownPrimes)
{
result.AddRange(KnownPrimes.Where(c => c < number).ToList());
if (number <= LargestValue)
{
return result;
}
result = KnownPrimes;
for (var i = LargestValue + 1; i <= number; i++)
{
var isPrime = true;
var n = Math.Floor(Math.Sqrt(i));
for (var j = 0; j < KnownPrimes.Count; j++)
{
var jVal = KnownPrimes[j];
if (jVal * jVal > i)
{
//isPrime = false;
break;
}
else if (i % jVal == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
result.Add(i);
}
}
LargestValue = number;
}
return result;
}
编辑:使用Sieve of Atkin要快得多，我对它进行了调整，以了解:
private static List<ulong> KnownPrimes = new List<long>();
private static ulong LargestValue = 1UL;
private unsafe static List<ulong> FindPrimes(ulong number)
{
var result = new List<ulong>();
var isPrime = new bool[number + 1];
var sqrt = Math.Sqrt(number);
lock (KnownPrimes)
{
fixed (bool* pp = isPrime)
{
bool* pp1 = pp;
result.AddRange(KnownPrimes.Where(c => c < number).ToList());
if (number <= LargestValue)
{
return result;
}
result = KnownPrimes;
for (ulong x = 1; x <= sqrt; x++)
for (ulong y = 1; y <= sqrt; y++)
{
var n = 4 * x * x + y * y;
if (n <= number && (n % 12 == 1 || n % 12 == 5))
pp1[n] ^= true;
n = 3 * x * x + y * y;
if (n <= number && n % 12 == 7)
pp1[n] ^= true;
n = 3 * x * x - y * y;
if (x > y && n <= number && n % 12 == 11)
pp1[n] ^= true;
}
for (ulong n = 5; n <= sqrt; n++)
if (pp1[n])
{
var s = n * n;
for (ulong k = s; k <= number; k += s)
pp1[k] = false;
}
if (LargestValue < 3)
{
KnownPrimes.Add(2);
KnownPrimes.Add(3);
}
for (ulong n = 5; n <= number; n += 2)
if (pp1[n])
KnownPrimes.Add(n);
LargestValue = number;
}
}
return result;
}
改编自原文
在添加项目时可以很容易地改进以获得更好的性能，但我建议您在执行之间将之前的KnownPrimes列表保存到磁盘，并加载一个预先存在的值列表，例如http://primes.utm.edu/lists/small/millions中的列表- Credit归CodingBarfield
我找到了这个链接:
http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm根据你的问题，似乎你感兴趣的不是证明某个给定的数字可能(或肯定)是素数，你也对分解大数不感兴趣。要找到给定N以内的所有素数，可以使用埃拉托色尼筛，但在上面的链接中似乎考虑了进一步的优化。
我认为一个相关的问题是"上限会有多大"。如果数字在一个相对较小的范围内[比如2^16]，你可能只是预先计算并保存所有质数(低于某些限制)到文件中，然后在适当的地方加载到内存中(然后可能继续使用下面列出的筛分之一)。
Ivan Benko和Steve Jessop上面提到了两种更著名的快速方法[Eratosthenes, Atkin]，尽管Ivan认为Sieve的复杂度是O(n*log(log(n)))。
Sieve相对容易实现，并且与您的方法相比非常快。
绝对最高效:
(最小化工作以获得结果)。
将域内所有数字的素数存储在以数字为键的哈希表中