gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:45:59 24 4
gpt4 key购买 nike

我要解决的问题是在 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 的准确性

最佳答案

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

关于c# - 准确的 "Sieve of Erathostenes"在C#中判断BigInteger的素数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23106719/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com