Anonymous user
Miller–Rabin primality test: Difference between revisions
Python added (from bc)
(add Tcl) |
(Python added (from bc)) |
||
Line 281:
''Possible improvements'': create bindings to the [[:Category:GMP|GMP library]], change <code>integer(huge)</code> into something like <code>type(huge_integer)</code>, write a lots of interfaces to allow to use big nums naturally (so that the code will be unchanged, except for the changes said above)
=={{header|Python}}==
<lang python>>>> import random
>>> def miller_rabin (n,k):
if n<=3: return True
if n % 2 == 0: return False
d = n - 1
s = 0
while d%2 == 0:
d = d / 2
s += 1
while k >0:
k -= 1
a = random.randrange(2,n-1)
x = a**d % n
if x != 1:
for r in range(s):
if x == n-1:
break
x = x*x % n
if x != n-1:
return False
return True
>>> [ i for i in range(1,1000) if miller_rabin(i, 10)][-10:]
[937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
>>> </lang>
=={{header|Smalltalk}}==
| |||