Anonymous user
Miller–Rabin primality test: Difference between revisions
→Python: Proved correct up to large N: Better generation of initial _known_primes
(→{{header|Haskell}}: Marked incorrect) |
(→Python: Proved correct up to large N: Better generation of initial _known_primes) |
||
Line 1,927:
return False
return True # n is definitely composite
def is_prime(n, _precision_for_huge_n=16):
Line 1,956 ⟶ 1,953:
# otherwise
return not any(_try_composite(a, d, n, s)
for a in _known_primes[:_precision_for_huge_n])
_known_primes = [2, 3]
_known_primes += [x for x in range(5, 1000, 2) if is_prime(x)]</lang>
;Testing:
Using the test values from the Ada
<pre>>>> is_prime(4547337172376300111955330758342147474062293202868155909489)
True
>>> is_prime(4547337172376300111955330758342147474062293202868155909393)
False
>>> [x for x in range(901, 1000) if is_prime(x)]
[907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
>>> </pre>
| |||