精确的“；Erathostenes筛”；以确定C#中BigInteger的素性

本文关键字：BigInteger Erathostenes | 更新日期: 2023-09-27 17:58:30

我试图解决的问题是在C#中找到任意长数（BigInteger）的素性。为了完成这项任务，我实施了"Erathostene筛"。该算法已经很快了，但就准确性而言，我持怀疑态度，因为我不确定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 的准确性

精确的“；Erathostenes筛”；以确定C#中BigInteger的素性

Erathostene的筛分工作如下：

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

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

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

要检查一个数字是否是素数，我们可以有一种更简单的方法，而不是使用Erathostenes筛，这只适用于生成素数列表的情况。

伪代码：

boolean isPrime(int num){
    for(int i = 2; i*i <= num ; i++){
        if(num % i == 0){
           return false;
        }            
    }
    return true;
}
相关文章：