きったんの頭_ん中☆

#! /usr/bin/env python3
"""
Listing Prime Numbers
https://mind.kittttttan.info/py/prime
"""
from random import randint
from time import time

def getPrimes(n):
    """
    Get prime numbers.
    n is length of the list.
    """
    if n >= 2:
        list = [3]
        length = 2
        i = 5
        while length < n:
            j = 0
            while list[j] * list[j] <= i:
                if not (i % list[j]):
                    break
                j += 1
            else:
                list.append(i)
                length += 1
            i += 2
        return [2]+list
    if n > 0:
        return [2]
    return []

def getPrime(n):
    """
    Get nth prime number.
    n is index of the prime.
    """
    if n >= 2:
        list = [3]
        length = 2
        i = 5
        while length < n:
            j, f = 0, True
            while list[j]*list[j] <= i:
                if not (i % list[j]):
                    f = False
                    break
                j += 1
            if f:
                list.append(i)
                length += 1
            i += 2
        return list[length - 2]
    if n > 0:
        return 2
    return None

def sieve(n):
    """
    Get primes below n
    """
    s = [True] * (n + 1)
    s[0], s[1] = False, False
    sqrtn = int(n**0.5)
    for i in range(2, sqrtn+1):
        if s[i]:
            m = n//i - i
            s[i*i : n+1 : i] = [False] * (m+1)
    return [i for i in range(n+1) if s[i]]

def mrpt(n, times=20):
    """
    Miller-Rabin primality test.
    If n looks like prime then return True.
    """
    if n == 2:
        return True
    if not n & 1:
        return False
    if not n > 2:
        return False
    d = n - 1
    while not (d & 1):
        d >>= 1
    for i in range(times):
        a = randint(1, n - 1)
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = pow(y, 2, n)
            t <<= 1
        if y != n - 1 and not (t & 1):
            return False
    return True

def test1():
    print('\n-- test1 --')
    limit = int(input('Input limit: '))

    t1 = time()
    p = getPrime(limit)
    t2 = time()

    print('%sth prime is %s' % (limit, p))
    print('%ss' % (t2 - t1))

def test2():
    print('\n-- test2 --')
    f = 7000
    l = 7100
    t1 = time()

    print('Primes from %s to %s' % (f,l))
    for i in range(f,l):
        if mrpt(i):
            print(i)

    t2 = time()
    print('%ss' % (t2 - t1))

def test3():
    print('\n-- test3 --')
    l = int(input('Input limit: '))

    t1 = time()
    ps = sieve(l)
    t2 = time()

    print('Max prime below %s is %s' % (l, ps[len(ps) - 1]))

    print('%ss' % (t2 - t1))

def main():
    test1()
    test2()
    test3()

if __name__ == "__main__":
    main()
きったんの頭ん中☆

きったんの頭_ん中☆
