RosettaCodeData/Task/Pierpont-primes/Python/pierpont-primes.py

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()