71 lines
1.7 KiB
Python
71 lines
1.7 KiB
Python
from random import randrange
|
|
|
|
# Copied from https://rosettacode.org/wiki/Miller-Rabin_primality_test#Python
|
|
def is_Prime(n: int):
|
|
"""
|
|
Miller-Rabin primality test.
|
|
|
|
A return value of False means n is certainly not prime. A return value of
|
|
True means n is very likely a prime.
|
|
"""
|
|
#Miller-Rabin test for primes
|
|
if n in [2,3,5,7]:
|
|
return True
|
|
elif n<10:
|
|
return False
|
|
|
|
s = 0
|
|
d = n-1
|
|
while d%2==0:
|
|
d>>=1
|
|
s+=1
|
|
assert(2**s * d == n-1)
|
|
|
|
def trial_composite(a):
|
|
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
|
|
|
|
for i in range(8):#number of trials
|
|
a = randrange(2, n)
|
|
if trial_composite(a):
|
|
return False
|
|
|
|
return True
|
|
|
|
def pierpont(ulim, vlim, first):
|
|
p = 0
|
|
p2 = 1
|
|
p3 = 1
|
|
pp = []
|
|
for v in range(vlim):
|
|
for u in range(ulim):
|
|
p = p2 * p3
|
|
if first:
|
|
p = p + 1
|
|
else:
|
|
p = p - 1
|
|
if is_Prime(p):
|
|
pp.append(p)
|
|
p2 = p2 * 2
|
|
p3 = p3 * 3
|
|
p2 = 1
|
|
pp.sort()
|
|
return pp
|
|
|
|
def main():
|
|
print("First 50 Pierpont primes of the first kind:")
|
|
pp = pierpont(120, 80, True)
|
|
for i in range(50):
|
|
print("%8d " % pp[i], "\n"*((i - 9) % 10 == 0), end="")
|
|
print("First 50 Pierpont primes of the second kind:")
|
|
pp2 = pierpont(120, 80, False)
|
|
for i in range(50):
|
|
print("%8d " % pp2[i], "\n"*((i - 9) % 10 == 0), end="")
|
|
print("250th Pierpont prime of the first kind:", pp[249])
|
|
print("250th Pierpont prime of the second kind:", pp2[249])
|
|
|
|
main()
|