费马素性测试

Question

我曾尝试为Fermat素性测试编写代码,但显然失败了.所以,如果我深知:如果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;
    }

Answer 1

阅读对维基百科的文章费马素性测试，你必须选择的a是少比候选您正在测试，而不是更多。

此外，正如 MattW 评论的那样，只测试一个a不会给你一个关于候选人是否是素数的结论性答案。a在确定一个数可能是质数之前，您必须测试许多可能的s。即便如此，有些数字可能看起来是素数，但实际上是合数。