Zis si facut ... am implementat algoritmul in C (pentru problema
Dk mai intai), dar mi-l ia pe 9 ca numar prim, pana si algoritmul in sine de pe pagina lor de wikipedia.
Python putin modificat, dar structura algoritmului e aceeasi:
import random
import math
def miller_rabin(n):
k = 1000
s = max(f for f in range(0, int(math.log(n,2))) if (n-1) % 2**f == 0)
d = (n-1) / 2**s
for i in xrange(k):
a = random.randrange(2, n-1)
x = pow(a, d, n)
if x == 1 or x == n-1:
continue
for r in range(1, s+1):
if x == s:
return False
x = pow(x, 2, n)
if x == 1:
return False
if x == n-1:
break
return True
print filter(miller_rabin, range(5, 100, 2))
Si implementarea in C (mai e loc de optimizari):
http://pastebin.com/5e8e9dWhAm verificat si algoritmul din pseudocod cu bazele 2 7 si 61 (care merg corect pe numere sub 4 miliarde) dar mi-l ia si aici pe 9 (posibil si altele) oricum pe problema Dk iau cateva WA in rest numai TLE
.