数学のプレートの学習の大きい素数はMiller〓を検査測定します.Rabinアルゴリズム

Miller_Rabinアルゴリズム
アルゴリズムの二つの基礎理論:

フィマ小定理:pが素数である場合、a^(p-1)＝1(mod p)がありますが、逆に成立するとは限りません.

の二次探知:一素数p、対0

証明:Miller-Rabin素性テストアルゴリズム詳細
問題の解き方

特判0,1,2,偶数

n-1=u*2^t(uは奇数)

は、ランダムに1つの数aを選択し、1 a^（p-1）＝1（mod p）（フェ馬小定理）成立は継続し、不成立はfalseに戻る。

を命令する.

令x=a^u%n、後t回循環(循環後x=a^(n-1)サイクル中x

サイクル終了x=a^(n-1)もしx!1,nは合数

である.

多ランダム何回かaを使って、精度を上げる

.
コードテンプレート:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define me(x,y) memset(x,y,sizeof x)
#define MIN(x,y) x < y ? x : y
#define MAX(x,y) x > y ? x : y
typedef long long ll;
const int maxn = 1e5+10;
const double INF = 0x3f3f3f3f;
const int MOD = 1e6;
const double eps = 1e-06;

ll Quick_Multiply(ll a,ll b,ll p){  // a*b%p
    ll ans = 0;
    a %= p;
    b %= p;
    if(b < 0) a = -a,b = -b;
    while(b){
        if(b&1) ans = (ans+a)%p;
        b >>= 1;
        a = (a+a)%p;
    }
    ans = (ans+p)%p;
    return ans;
}

ll Quick_Pow(ll a,ll b,ll p){   //a^b%p
    ll ans = 1;
    while(b){
        if(b&1) ans = Quick_Multiply(ans,a,p)%p;
        b >>= 1;
        a = Quick_Multiply(a,a,p)%p;
    }
    return ans;
}

bool Miller_Rabin(ll n){    //Miller_Rabin
    ll i,j,a,x,y,t,u,s = 10;
    if(n == 2 || n == 3) return true;
    if(n < 2 || !(n&1)) return false;
    for(t = 0,u = n-1;!(u&1); t++,u>>=1);   //n-1 = u*2^t
    for(i = 0; i < s; i++){
        a = rand()%(n-1)-1;
        x = Quick_Pow(a,u,n);   //a^u
        for(j = 0; j < t; j++){
            y = Quick_Multiply(x,x,n);  //x^2
            if(y == 1 && x != 1 && x != n-1) return false;  //    
            x = y;
        }
        if(x != 1) return false;    //     
    }
    return true;
}
int main(){
    
    //freopen("E:/TanJX/in.txt","r",stdin);
    //freopen("E:/TanJX/out.txt","w",stdout);
    int n;
    while(cin>>n){
        int sum = 0;
        ll x;
        for(int i = 1; i <= n; i++){
            scanf("%lld",&x);
            if(Miller_Rabin(x)) sum++;
        }
        cout<<sum<<endl;
    }
    return 0;
}


/*


*/