31 lines
1.2 KiB
Python
31 lines
1.2 KiB
Python
import random
|
|
|
|
|
|
def try_comp(a, d, n, s):
|
|
if pow(a, d, n) == 1:
|
|
return False
|
|
for i in range(s):
|
|
if pow(a, 2 ** i * d, n) == n - 1:
|
|
return False
|
|
return True
|
|
|
|
|
|
def primetest(n, r=15):
|
|
if n < 3: return n == 2
|
|
if n % 2 == 0: return False
|
|
s, d = 0, n - 1
|
|
while True:
|
|
quo, rem = divmod(d, 2)
|
|
if rem == 1:
|
|
break
|
|
s, d = s + 1, quo
|
|
|
|
for i in range(r):
|
|
if try_comp(random.randrange(2, n), d, n, s):
|
|
return False
|
|
return True
|
|
|
|
|
|
print(primetest(
|
|
16826274250898468911280407749426542060694768486649616295792750595928899095760198861413145674011622196806001189975331140430984389138737798839798102100501250562384543970148324519320707086782480622768727739619400406298163697633506711667490859272493284358461677857576459592581649298303621108919528607436653031634208416252311924449922771895182310841019584155318547423916714195019363678142800559476884532645915293106647126449661258738488043253150745449466402688849719911594517744984668897073482226741417140010936686564467276499458185350171327208056715254738641774818774823242004784520937289671279357019604426730692283732729))
|
|
print(primetest(2938475483920938745789028764))
|