素数判定法——MR素性测试

1. /*
2. * @Author: Gehrychiang
3. * @LastEditors : Please set LastEditors
4. * @Website: www.yilantingfeng.site
5. * @E-mail: gehrychiang@aliyun.com
6. */
7. #include <bits/stdc++.h>
8. using namespace std;
10. long long fastMul(long long a, long long b, long long mod) //a*b % mod
11. {
12. long long res = 0;
13. while (b)
14. {
15. if (b & 1)
16. {
17. res = (res + a) % mod;
18. }
19. a = (a + a) % mod;
20. b >>= 1;
21. }
22. return res;
23. }
25. long long fastPowMod(long long a, long long n, long long mod) //a^n % mod
26. {
27. if (n == 0 && a != 0)
28. return 1;
29. if (n != 0 && a == 0)
30. return 0;
31. long long base = a;
32. long long res = 1;
33. while (n)
34. {
35. if (n & 1)
36. {
37. res = fastMul(res, base, mod);
38. }
39. base = fastMul(base, base, mod);
40. n >>= 1;
41. }
42. return res % mod;
43. }
45. bool mr_test(long long n, long long a, long long d)
46. {
47. if (n == 2) //n是2
48. return true;
49. if (n % 2 == 0) //n为偶数
50. return false;
51. if (n == a) //二者相等了，其实这种情况并不会出现，已经在组测试中得到了True的返回值
52. return false;
53. // 存在某个i使得a^(d*2^i) mod n=n-1 i>=0
54. while (!d & 1) //确保d为奇数
55. {
56. d >>= 1; // d/=2
57. }
58. long long t = fastPowMod(a, d, n);
59. while (d != n - 1 && t != n - 1 && t != 1)
60. {
61. t = fastMul(t, t, n);
62. d <<= 1; // d*=2 这里用来还原前面的取成奇数的过程也就是把d朝n-1复原的过程
63. }
64. return t == n - 1 || t == 1; //如果最后我们的可以等于n-1或是为1那么就是通过了这一组测试
65. }
67. bool mr_test_grp(long long n)
68. {
69. if (n == 1)
70. return false;
71. int a[10] = {2, 3, 5, 7, 11, 13, 17, 19, 47, 61};
72. for (int i = 0; i < 10; i++)
73. {
74. if (n == a[i])
75. return true;
76. if (!mr_test(n, a[i], n - 1)) //有一组没通过素性测试
77. return false;
78. }
79. //更多的随机数样本测试，一般来说，工业级代码需要要求通过1k组以上的测试才能保证判断的准确性
80. // srand(5201314);
81. // for (int i = 0; i < 33; i++)
82. // {
83. // long long r=rand()%(n-1)+1;
84. // if(n==r)
85. // return true;
86. // if(!mr_test(n,r,n-1))
87. // return false;
88. // }
90. return true; //全部通过 此时大概率是素数
91. }
92. int main()
93. {
94. long long n;
95. cin >> n;
96. if (mr_test_grp(n))
97. {
98. cout << "yes" << endl;
99. }
100. else
101. {
102. cout << "no" << endl;
103. }
105. return 0;
106. }

/*
 * @Author: Gehrychiang
 * @LastEditors  : Please set LastEditors
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
#include <bits/stdc++.h>
using namespace std;

long long fastMul(long long a, long long b, long long mod) //a*b % mod
{
    long long res = 0;
    while (b)
    {
        if (b & 1)
        {
            res = (res + a) % mod;
        }
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}

long long fastPowMod(long long a, long long n, long long mod) //a^n % mod
{
    if (n == 0 && a != 0)
        return 1;
    if (n != 0 && a == 0)
        return 0;
    long long base = a;
    long long res = 1;
    while (n)
    {
        if (n & 1)
        {
            res = fastMul(res, base, mod);
        }
        base = fastMul(base, base, mod);
        n >>= 1;
    }
    return res % mod;
}

bool mr_test(long long n, long long a, long long d)
{
    if (n == 2) //n是2
        return true;
    if (n % 2 == 0) //n为偶数
        return false;
    if (n == a) //二者相等了，其实这种情况并不会出现，已经在组测试中得到了True的返回值
        return false;
    //  存在某个i使得a^(d*2^i) mod n=n-1  i>=0
    while (!d & 1) //确保d为奇数
    {
        d >>= 1; // d/=2
    }
    long long t = fastPowMod(a, d, n);
    while (d != n - 1 && t != n - 1 && t != 1)
    {
        t = fastMul(t, t, n);
        d <<= 1; // d*=2  这里用来还原前面的取成奇数的过程也就是把d朝n-1复原的过程
    }
    return t == n - 1 || t == 1; //如果最后我们的可以等于n-1或是为1那么就是通过了这一组测试
}

bool mr_test_grp(long long n)
{
    if (n == 1)
        return false;
    int a[10] = {2, 3, 5, 7, 11, 13, 17, 19, 47, 61};
    for (int i = 0; i < 10; i++)
    {
        if (n == a[i])
            return true;
        if (!mr_test(n, a[i], n - 1)) //有一组没通过素性测试
            return false;
    }
    //更多的随机数样本测试，一般来说，工业级代码需要要求通过1k组以上的测试才能保证判断的准确性
    // srand(5201314);
    // for (int i = 0; i < 33; i++)
    // {
    //     long long r=rand()%(n-1)+1;
    //     if(n==r)
    //     return true;
    //     if(!mr_test(n,r,n-1))
    //     return false;
    // }

    return true; //全部通过  此时大概率是素数
}
int main()
{
    long long n;
    cin >> n;
    if (mr_test_grp(n))
    {
        cout << "yes" << endl;
    }
    else
    {
        cout << "no" << endl;
    }

    return 0;
}