Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/*
The implementation of Miller-Rabin Test with C++
varified with ALDS1_1_C
http://joisino.hatenablog.com/entry/2017/08/03/210000
Copyright (c) 2017 joisino
Released under the MIT license
http://opensource.org/licenses/mit-license.php
*/
#include <bits/stdc++.h>
using namespace std;
struct Miller{
const vector<long long> v = { 2 , 7 , 61 }; // < 4,759,123,141
// x^k (mod m)
long long modpow( long long x, long long k, long long m ){
long long res = 1;
while( k ){
if( k & 1 ){
res = res * x % m;
}
k /= 2;
x = x * x % m;
}
return res;
}
// check if n is prime
bool check( long long n ){
if( n < 2 ){
return false;
}
long long d = n - 1;
long long s = 0;
while( d % 2 == 0 ){
d /= 2;
s++;
}
for( long long a : v ){
if( a == n ){
return true;
}
if( modpow( a , d , n ) != 1 ){
bool ok = true;
for( long long r = 0; r < s; r++ ){
if( modpow( a, d * (1LL << r), n ) == n-1 ){
ok = false;
break;
}
}
if( ok ){
return false;
}
}
}
return true;
}
};
Miller miller;
int main(){
int n, a;
int ans = 0;
scanf( "%d" , &n );
for( int i = 0 ; i < n; i++ ){
scanf( "%d" , &a );
if( miller.check( a ) ){
ans++;
}
}
printf( "%d\n" , ans );
// bench
/*
const int MAX_N = 1000000000;
const int loop = 1000000;
mt19937 mt( 1234 );
for( int i = 0; i < loop; i++ ){
int n = mt() % MAX_N;
miller.check( n );
}
*/
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.