C# 实现 Eratosthenes/Sundaram/Atkins 筛法
4.89/5 (17投票s)
C# 实现 Eratosthenes/Sundarm/Atkins 筛法以生成素数，并比较三种实现之间的性能。
介绍
本文详细介绍了使用四种著名算法生成素数。本文不讨论算法本身，而是讨论算法的优化实现。
- 穷举法
- 埃拉托斯特尼筛法
- 苏达兰筛法
- 阿特金筛法
背景
素数是“公钥密码学 (PKC)”的基础。 让我们深入了解 PKC，我将解释素数是如何使用的。
我们取两个素数 7 和 13，如果我想计算它们的乘积，我们可以轻松计算出 91。现在，假设我有一个数字 91，我想找到一对素数，它们的乘积等于 91；找到它们会比较困难，但最终我们可以找到。如果给定的数字是一个 128 位数字，那么快速找到它的因子将非常困难。
这种“因式分解困难”的素数问题被用作 PKC 的单向函数基础。
使用代码
穷举法 或试除法
穷举法是寻找素数的最简单方法。 为了确定一个数字是否为素数，我们将该数字与从 3 开始的奇数相除，并检查余数，直到奇数的平方小于我们要检查的数字。
如果没有余数，则该数字不是素数，否则就是。 下面的代码片段对此进行了检查。 `totalCount` 初始化为 1，因为 2 是素数，在我们的代码中被忽略。
int totalCount = 1;
bool isPrime = true;
for (long i = 3; i < topCandidate; i += 2)
{
for (int j = 3; j * j <= i; j += 2)
{
if ((i % j) == 0) { isPrime = false; break; }
}
if (isPrime) { totalCount++; } else isPrime = true;
}
return totalCount;
埃拉托斯特尼筛法
埃拉托斯特尼筛法是寻找素数的古老算法，也是第一个被编写出来的有效算法。
算法本身很简单。 假设我们要找到小于 10 的素数，创建一个长度为 10 的布尔数组，所有值都初始化为 true。 从 2 开始，将 2 的倍数在数组中设置为 false。 这个过程一直持续到数字的倍数小于 10。
最后，布尔数组中值为 true 的所有索引都被视为素数，除了索引 1。
初始数组 : 1 1 1 1 1 1 1 1 1 1
第一次遍历 (2 的倍数) : 1 1 1 0 1 0 1 0 1 0
第二次遍历 (3 的倍数) : 1 1 1 0 1 0 1 0 0 0
第三次遍历 (4 的倍数) : 1 1 1 0 1 0 1 0 0 0
第四次遍历 (5 的倍数) : 1 1 1 0 1 0 1 0 0 0
第五次遍历不再可能，因为 6 的倍数大于 10。素数是 2、3、5 和 7。
int totalCount = 0;
BitArray myBA1 = new BitArray(topCandidate + 1);
/* Set all but 0 and 1 to prime status */
myBA1.SetAll(true);
myBA1[0] = myBA1[1] = false;
/* Mark all the non-primes */
int thisFactor = 2;
int lastSquare = 0;
int thisSquare = 0;
while (thisFactor * thisFactor <= topCandidate)
{
/* Mark the multiples of this factor */
int mark = thisFactor + thisFactor;
while (mark <= topCandidate)
{
myBA1[mark] = false;
mark += thisFactor;
}
/* Print the proven primes so far */
thisSquare = thisFactor * thisFactor;
for (; lastSquare < thisSquare; lastSquare++)
{
if (myBA1[lastSquare]) totalCount++;
}
/* Set thisfactor to next prime */
thisFactor++;
while (!myBA1[thisFactor]) { thisFactor++; }
}
/* Print the remaining primes */
for (; lastSquare <= topCandidate; lastSquare++)
{
if (myBA1[lastSquare]) { totalCount++; }
} 此算法比穷举法有效，但像任何其他素数计算算法一样，受到内存限制。
苏达兰筛法
苏达兰筛法比埃拉托斯特尼筛法更有效。 它使用与埃拉托斯特尼筛法类似的筛法原理，但不考虑偶数。
它会划掉筛法 (布尔数组) 中任何形式为 i+j+2ij 且 i+j+2ij <=n 的数字
其中 n 是我们要找出其下所有素数的数字。
i >= 1 且小于 < n/2
j >= i 且小于 n
最后，筛法中值为 true 的索引乘以 2 再加 1 即可得到素数。 下面是 SOS 的优化实现。
/* SEIVE */
int maxVal = 0;
int denominator = 0;
for (int i = 1; i < k; i++)
{
denominator = (i << 1) + 1;
maxVal = (k - i) / denominator;
for (int j = i; j <= maxVal; j++)
{
myBA1[i + j * denominator] = false;
}
}
int prime= 0;
for (int i = 1; i < k; i++)
{
if (myBA1[i])
{
totalCount++;
prime= (i << 1) + 1;
}
}
性能优于埃拉托斯特尼筛法，但在内存限制方面，其问题是埃拉托斯特尼筛法的一半。
阿特金筛法
阿特金筛法是对埃拉托斯特尼筛法的改进。 它不通过所有数字来判断其是否为素数，而是依赖于二次方程和模 60 来找出素数/非素数的模式，并在布尔数组中标记它们。
下面的代码实现了阿特金筛法。
int totalCount = 0;
BitArray isPrime = new BitArray(topCandidate + 1);
int squareRoot = (int)Math.Sqrt(topCandidate);
int xSquare = 1, xStepsize = 3;
int ySquare = 1, yStepsize = 3;
int computedVal = 0;
for (int x = 1; x <= squareRoot; x++)
{
ySquare = 1;
yStepsize = 3;
for (int y = 1; y <= squareRoot; y++)
{
computedVal = (xSquare << 2) + ySquare;
if ((computedVal <= topCandidate) && (computedVal % 12 == 1 || computedVal % 12 == 5))
isPrime[computedVal] = !isPrime[computedVal];
computedVal -= xSquare;
if ((computedVal <= topCandidate) && (computedVal % 12 == 7))
isPrime[computedVal] = !isPrime[computedVal];
if (x > y)
{
computedVal -= ySquare << 1;
if ((computedVal <= topCandidate) && (computedVal % 12 == 11))
isPrime[computedVal] = !isPrime[computedVal];
}
ySquare += yStepsize;
yStepsize += 2;
}
xSquare += xStepsize;
xStepsize += 2;
}
for (int n = 5; n <= squareRoot; n++)
{
if (isPrime[n] == true)
{
int k = n * n;
for (int z = k; z <= topCandidate; z += k)
isPrime[z] = false;
}
}
for (int i = 1; i < topCandidate; i++)
{
if (isPrime[i]) totalCount++;
}
return (totalCount + 2); // 2 and 3 will be missed in Sieve Of Atkins 上述代码比埃拉托斯特尼筛法更有效，在某些情况下与苏达兰筛法相同或效率稍差。 这是因为对不相关的数字进行了不必要的计算。
假设我们需要找出 10 以下的所有素数。 4x^2+y^2 需要对小于 10 的平方根（即 3）的所有数字进行计算。 Operation 4 * (3^2) + 1 ^ 2 , 4 * (3^2) + 2 ^ 2 ,4 * (3^2) + 3 ^ 2 是不必要的，因为结果大于 10。在正常实现中无法删除这一点。
在提供的代码中，提供了一个优化实现，它将忽略不必要的计算，但同时也更难理解。
兴趣点
- 所有算法的更有效实现。
- 通过使用分页、机器集群来克服内存限制，并能快速找到符合密码学标准的素数。