c# - 准确的 "Sieve of Erathostenes"在C#中判断BigInteger的素数

Question

我要解决的问题是在 C# 中找到任意长数 ( BigInteger) 的素数。为了完成这个任务，我已经执行了“Sieve of Erathostenes”。该算法已经很快，但就准确性而言，我持怀疑态度，因为我不确定 BigInteger 在表示任意长数字时的准确性。

“Erathostenes 筛法”算法

public static bool IsPrime(BigInteger value)
{
    int result = 0;
    // 2, 3, 5 and 7 are the base primes used in the Sieve of Erathostenes
    foreach (int prime in new int[] { 2, 3, 5, 7 })
    {
        // If the value is the base prime, it's prime - no further calculation required.
        if (value == prime)
        {
            return true;
        }

        // Else, we need to work out if the value is divisible, by any of these primes...
        BigInteger remainder = 0;
        BigInteger.DivRem(value, prime, out remainder);

        if (remainder != 0)
        {
            // We increment result to indicate that the value was not divisible by the base prime
            result++;
        }
    }

    // If result is 4, thus, not divisible my any of the base primes, it must be prime.
    return result == 4;
}

我的问题不是“为什么我的代码不工作”——它更像是“这是否准确地确定了 BigInteger 的素数”

具体来说，我想知道 BigInteger.DivRem 的准确性

Answer 1

Erathostenes 筛的工作原理如下:

• 首先假设所有数字都是素数。

• 从2开始，划掉所有是2的倍数的数字。然后，移动到下一个没有被划掉的数，去掉这个数的所有倍数，以此类推……所以，最后剩下的就是素数列表。

很明显，您的代码不是 Erathostenes 筛法，您假设素数列表只有 2,3,5,7

要检查一个数是否是素数，我们可以有一个更简单的方法，而不是使用埃拉托斯特内斯筛法，它只适用于您想要生成素数列表的情况。

伪代码:

boolean isPrime(int num){

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