c# – 费马素性测试

发布时间：2020-12-15 04:09:43 所属栏目：百科来源：网络整理

导读：我曾尝试为 Fermat primality test编写代码,但显然失败了. 所以如果我理解得很好：如果p是素数那么((a ^ p)-a)％p = 0其中p％a！= 0. 我的代码似乎没问题,因此我很可能误解了基础知识.我在这里错过了什么？ private bool IsPrime(int candidate) { //checkin

我曾尝试为 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可能看起来是素数但实际上是复合的.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!