准确的“Erathostenes筛选”来确定C＃中BigInteger的素数

The problem I am trying to solve is to find the primality of an arbitrarily long number (BigInteger) in C#. To achieve this task, I have implemented the "Sieve of Erathostenes". The algorithm is already fast, but in terms of accuracy, I am skeptical as I am unsure of how accurate BigInteger is in representing arbitrarily long numbers.

我试图解决的问题是在C＃中找到任意长数（BigInteger）的素数。为了完成这项任务，我实施了“Erathostenes筛选”。该算法已经很快，但就准确性而言，我持怀疑态度，因为我不确定BigInteger在表示任意长数方面有多准确。

The "Sieve of Erathostenes" algorithm

“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;
}

My question is not "why is my code not working" - it's more "is this accurately determining primality of BigInteger"

我的问题不是“为什么我的代码不能正常工作” - 更多的是“这是否准确地确定了BigInteger的原始性”

Specifically, I would like to know about the accuracy of BigInteger.DivRem

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

1 个解决方案

#1

Sieve of Erathostenes is work as follow:

Erathostenes筛选的工作如下：

First assume that all numbers is prime.

首先假设所有数字都是素数。
Starting from 2, crossing out all the numbers that is a multiple of two. Then, move to the next number that is not crossed out, and remove all multiple of this number, and so on... so, in the end what is left is the list of prime number.

从2开始，越过所有数字，即2的倍数。然后，移动到下一个未划掉的数字，并删除该数字的所有多个，依此类推......所以，最后剩下的是素数列表。

So clearly, your code is not Sieve of Erathostenes, which you made an assumption that the list of prime is only 2,3,5,7

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

To check whether a number is a prime or not, we can have a more easy way, instead of using Sieve of Erathostenes, which is only suitable when you want to generate a list of prime numbers.

要检查数字是否为素数，我们可以采用更简单的方法，而不是使用Erathostenes筛选，这仅适用于您想要生成素数列表的情况。

Pseudo Code:

伪代码：

boolean isPrime(int num){

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

#1