我曾尝试为
Fermat primality test编写代码,但显然失败了.
所以如果我理解得很好：如果p是素数那么((a ^ p)-a)％p = 0其中p％a！= 0.
我的代码似乎没问题,因此我很可能误解了基础知识.我在这里错过了什么？
所以如果我理解得很好：如果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可能看起来是素数但实际上是复合的.
