Anonymous user
Miller–Rabin primality test: Difference between revisions
added for Language PIKE
(Add Nim version (translated from Go)) |
(added for Language PIKE) |
||
Line 4,568:
zkl: BN("4547337172376300111955330758342147474062293202868155909393").probablyPrime()
False</lang>
=={{header|PIKE}}==
<lang PIKE>
int pow_mod(int m, int i,int mod){
int x=1,y=m%mod;
while(i){
if(i&1) x = x*y%mod;
y = y*y%mod;
i>>=1;
}
return x;
}
bool mr_pass(int a, int s, int d, int n){
int a_to_power = pow_mod(a, d, n);
if(a_to_power == 1)
return true;
for(int i = 0; i< s - 1; i++){
if(a_to_power == n - 1)
return true;
a_to_power = (a_to_power * a_to_power) % n;
}
return a_to_power == n - 1;
}
int is_prime(int n){
array(int) prime ;
prime = ({2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 61, 67, 71, 79, 83, 89, 97, 101, 103, 107, 109, 113});
int idx = search( prime, n);
if( n < 113 && n == prime[idx] ){
return 1;
}
if(n < 2047) prime = ({2, 3});
if(n < 1373653)prime = ({2, 3});
if(n < 9080191)prime = ({31, 73});
if(n < 25326001)prime = ({2, 3, 5});
if(n < 3215031751)prime = ({2, 3, 5, 7});
if(n < 4759123141)prime = ({2, 7, 61});
if(n < 1122004669633)prime = ({2, 13, 23, 1662803});
if(n < 2152302898747)prime = ({2, 3, 5, 7, 11});
if(n < 3474749660383)prime = ({2, 3, 5, 7, 11, 13});
if(n < 341550071728321)prime = ({2, 3, 5, 7, 11, 13, 17});
if(n < 3825123056546413051)prime = ({2, 3, 5, 7, 11, 13, 17, 19, 23});
if(n < 18446744073709551616)prime = ({2, 3, 5, 7, 11, 13, 17, 19, 23, 29});
if(n < 318665857834031151167461)prime = ({2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31});
if(n < 3317044064679887385961981)prime = ({2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37});
else prime = ({2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 61, 67, 71});
int d = n - 1;
int s = 0;
while(d % 2 == 0){
d >>= 1;
s += 1;
}
for (int repeat=0 ; repeat < sizeof(prime); repeat++){
int a = prime[repeat];
if(!mr_pass(a, s, d, n)){
return 0;
}
}
return 1;
}
int main() {
array(int) lists;
lists =({35201546659608842026088328007565866231962578784643756647773109869245232364730066609837018108561065242031153677,
10513733234846849736873637829838635104309714688896631127438692162131857778044158273164093838937083421380041997,
24684249032065892333066123534168930441269525239006410135714283699648991959894332868446109170827166448301044689,
76921421106760125285550929240903354966370431827792714920086011488103952094969175731459908117375995349245839343,
32998886283809577512914881459957314326750856532546837122557861905096711274255431870995137546575954361422085081,
30925729459015376480470394633122420870296099995740154747268426836472045107181955644451858184784072167623952123,
14083359469338511572632447718747493405040362318205860500297736061630222431052998057250747900577940212317413063,
10422980533212493227764163121880874101060283221003967986026457372472702684601194916229693974417851408689550781,
36261430139487433507414165833468680972181038593593271409697364115931523786727274410257181186996611100786935727,
15579763548573297857414066649875054392128789371879472432457450095645164702139048181789700140949438093329334293});
for(int i=0;i<sizeof(lists);i++){
int n = lists[i];
int chk = is_prime(n);
if(chk == 1) write(sprintf("%d %s\n",n,"PRIME"));
else write(sprintf("%d %s\n",n,"COMPOSIT"));
}
}
TEST
35201546659608842026088328007565866231962578784643756647773109869245232364730066609837018108561065242031153677 PRIME
10513733234846849736873637829838635104309714688896631127438692162131857778044158273164093838937083421380041997 PRIME
24684249032065892333066123534168930441269525239006410135714283699648991959894332868446109170827166448301044689 PRIME
76921421106760125285550929240903354966370431827792714920086011488103952094969175731459908117375995349245839343 PRIME
32998886283809577512914881459957314326750856532546837122557861905096711274255431870995137546575954361422085081 PRIME
30925729459015376480470394633122420870296099995740154747268426836472045107181955644451858184784072167623952123 PRIME
14083359469338511572632447718747493405040362318205860500297736061630222431052998057250747900577940212317413063 PRIME
10422980533212493227764163121880874101060283221003967986026457372472702684601194916229693974417851408689550781 PRIME
36261430139487433507414165833468680972181038593593271409697364115931523786727274410257181186996611100786935727 PRIME
15579763548573297857414066649875054392128789371879472432457450095645164702139048181789700140949438093329334293 PRIME
</lang>
| |||