Miller-Rabin素数检测算法

遇到了一个题：

^Description:

Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics. It states:

Every even integer greater than 2 can be expressed as the sum of two primes.

The actual verification of the Goldbach conjecture shows that even numbers below at least 1e14 can be expressed as a sum of two prime numbers.

Many times, there are more than one way to represent even numbers as two prime numbers.

For example, 18=5+13=7+11, 64=3+61=5+59=11+53=17+47=23+41, etc.

Now this problem is asking you to divide a postive even integer n (2<n<2^63) into two prime numbers.

Although a certain scope of the problem has not been strictly proved the correctness of Goldbach's conjecture, we still hope that you can solve it.

If you find that an even number of Goldbach conjectures are not true, then this question will be wrong, but we would like to congratulate you on solving this math problem that has plagued humanity for hundreds of years.

Input:

The first line of input is a T means the number of the cases.

Next T lines, each line is a postive even integer n (2<n<2^63).

Output:

The output is also T lines, each line is two number we asked for.

T is about 100.

本题答案不唯一，符合要求的答案均正确

样例输入

1

8

样例输出

3 5


题解：预处理1e6范围的素数，暴力这些素数ai 利用素数判定n-ai是否是素数
预处理：线性筛法的模板

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e6+;

bool check[maxn];

int prime[maxn];

int main(){

    int i,j,pos=,flag;

    for(i=;i<maxn;i++){

        if(!check[i]) prime[pos++]=i;

        for(j=;j<pos&&i*prime[j]<maxn;j++){

            check[i*prime[j]]=true;

            if(i%prime[j]==) break;

        }

    }

然后就是素数的判断

以下摘录博客：

https://blog.csdn.net/zengaming/article/details/51867240

https://www.cnblogs.com/SinGuLaRiTy2001/p/6591414.html

先说几个理论基础：

1. 费马小定理：假如p是质数，a是整数，且a、p互质，那么a的(p-1)次方除以p的余数恒等于1，即：a^(p-1)≡1(mod p).

但是反过来却不一定成立，就是说，如果a、p互质，且a^(p-1)≡1(mod p)，不能推出p是质数，比如Carmichael数。

2. 二次探测定理：如果p是一个素数，0<x<p,则方程x^2≡1(mod p)的解为x=1或x=p-1。

3. 模运算的规则：(a*b)%n=(a%n * b%n)%n

4. 快速积取模、快速幂取模：可以看看我之前写的一篇博客简单快速的算法

这些理论基础还没有好好想过。。

然后是算法的过程：

对于要判断的数n

1.先判断是不是2，是的话就返回true。

2.判断是不是小于2的，或合数，是的话就返回false。

3.令n-1=u*2^t，求出u，t，其中u是奇数。

4.随机取一个a,且1<a<n

/*根据费马小定理，如果a^(n-1)≡1(mod p)那么n就极有可能是素数，如果等式不成立，那肯定不是素数了

因为n-1=u*2^t，所以a^(n-1)=a^(u*2^t)=(a^u)^(2^t)。*/

5.所以我们令x=(a^u)%n

6.然后是t次循环，每次循环都让y=(x*x)%n，x=y,这样t次循环之后x=a^(u*2^t)=a^(n-1)了

7.因为循环的时候y=(x*x)%n，且x肯定是小于n的，正好可以用二次探测定理，

如果(x^2)%n==1，也就是y等于1的时候，假如n是素数，那么x==1||x==n-1，如果x!=1&&x!=n-1，那么n肯定不是素数了，返回false。

8.运行到这里的时候x=a^(n-1)，根据费马小定理，x!=1的话，肯定不是素数了，返回false

9.因为Miller-Rabin得到的结果的正确率为 75%，所以要多次循环步骤4~8来提高正确率

10.循环多次之后还没返回，那么n肯定是素数了，返回true

下面是模板：

const ll S = ;

ll mult_mod(ll a, ll b, ll c) {

    a %= c;

    b %= c;

    ll ret = ;

    ll tmp = a;

    while (b) {

        if (b & ) {

            ret += tmp;

            if (ret > c) ret -= c;

        }

        tmp <<= ;

        if (tmp > c)tmp -= c;

        b >>= ;

    }

    return ret;

}

ll pow_mod(ll a, ll n, ll mod) {

    ll ret = ;

    ll temp = a % mod;

    while (n) {

        if (n & )ret = mult_mod(ret, temp, mod);

        temp = mult_mod(temp, temp, mod);

        n >>= ;

    }

    return ret;

}

bool check(ll a, ll n, ll x, ll t) {

    ll ret = pow_mod(a, x, n);

    ll last = ret;

    for (ll i = ; i <= t; i++) {

        ret = mult_mod(ret, ret, n);

        if (ret ==  && last !=  && last != n - )return true;

        last = ret;

    }

    if (ret != )return true;

    else return false;

}

bool Miller_Rabin(ll n) {

    if (n < )return false;

    if (n == )return true;

    if ((n & ) == )return false;

    ll x = n - ;

    ll t = ;

    while ((x & ) == ) {

        x >>= ;

        t++;

    }

    srand(time(NULL));

    for (ll i = ; i < S; i++) {

        ll a = rand() % (n - ) +;

        if (check(a, n, x, t))

            return false;

    }

    return true;

}

#include<cstdlib>

#include<ctime>

#include<cstdio>

using namespace std;

const int count=;

int modular_exp(int a,int m,int n)

{

    if(m==)

        return ;

    if(m==)

        return (a%n);

    long long w=modular_exp(a,m/,n);

    w=w*w%n;

    if(m&)

        w=w*a%n;

    return w;

}

bool Miller_Rabin(int n)

{

    if(n==)

        return true;

    for(int i=;i<count;i++)

    {

        int a=rand()%(n-)+;

        if(modular_exp(a,n,n)!=a)

            return false;

    }

    return true;

}

int main()

{

    srand(time(NULL));

    int n;

    scanf("%d",&n);

    if(Miller_Rabin(n))

        printf("Probably a prime.");

    else

        printf("A composite.");

    printf("\n");

 const ll S = ;

 ll mult_mod(ll a, ll b, ll c) {

     a %= c;

     b %= c;

     ll ret = ;

     ll tmp = a;

     while (b) {

         if (b & ) {

             ret += tmp;

             if (ret > c) ret -= c;

         }

         tmp <<= ;

         if (tmp > c)tmp -= c;

         b >>= ;

     }

     return ret;

 }

 ll pow_mod(ll a, ll n, ll mod) {

     ll ret = ;

     ll temp = a % mod;

     while (n) {

         if (n & )ret = mult_mod(ret, temp, mod);

         temp = mult_mod(temp, temp, mod);

         n >>= ;

     }

     return ret;

 }

 bool check(ll a, ll n, ll x, ll t) {

     ll ret = pow_mod(a, x, n);

     ll last = ret;

     for (ll i = ; i <= t; i++) {

         ret = mult_mod(ret, ret, n);

         if (ret ==  && last !=  && last != n - )return true;

         last = ret;

     }

     if (ret != )return true;

     else return false;

 }

 bool Miller_Rabin(ll n) {

     if (n < )return false;

     if (n == )return true;

     if ((n & ) == )return false;

     ll x = n - ;

     ll t = ;

     while ((x & ) == ) {

         x >>= ;

         t++;

     }

     srand(time(NULL));

     for (ll i = ; i < S; i++) {

         ll a = rand() % (n - ) +;

         if (check(a, n, x,

巴特西

Miller-Rabin素数检测算法

样例输入

样例输出

最新文章

热门文章