C# · 12月 26, 2021

c# – 费马素性测试

我曾尝试为 Fermat primality test编写代码,但显然失败了.
所以如果我理解得很好:如果p是素数那么((a ^ p)-a)%p = 0其中p%a!= 0.
我的代码似乎没问题,因此我很可能误解了基础知识.我在这里错过了什么? private bool IsPrime(int candidate) { //checking if candidate = 0 || 1 || 2 int a = candidate + 1; //candidate can’t be divisor of candidate+1 if ((Math.Pow(a,candidate) – a) % candidate == 0) return true; return false; }解决方法 阅读 Fermat primality test上的维基百科文章,您必须选择一个小于您正在测试的候选人的a,而不是更多.

此外,正如MattW评论的那样,只测试一个单一的a不会给你一个关于候选人是否是素数的确定答案.您必须先测试许多可能的内容,然后才能确定某个数字可能是素数.即使在那时,some numbers可能看起来是素数但实际上是复合的.