PrimeNumbers.py

import random
import math
from datetime import datetime

def eco_pov(a, d, p):
    res = a % p
    d -= 1
    while d > 0:
        res *= a
        res %= p
        d -= 1
    return res


def is_prime1(p):
    m = 10
    count = 0
    only1 = True
    while m > 0:
        m -= 1

        a = random.randint(1, p)
        k = eco_pov(a, int((p-1)/2), p)
        print("\t%d\t%d" % (a,k))

        if not (k == 1 or k == p-1):
            return False
        if (k == p-1):
            only1 = False
    return not only1


def is_prime2(n):
    if n % 2 == 0:
        return False
    n -= 1
    d = n
    s = 0
    while d % 2 == 0:
        d /= 2
        s += 1
    m = math.log2(n)
    while m > 0:
        a = random.randint(2, n)
        z = eco_pov(a, d, n+1)
        if z == 1 or z == n:
            break
        flag = False
        for j in range(1, s-1):
            flag = eco_pov(z, 2**j, n+1) == n
            if flag:
                break
        if not flag:
            return False
        m -= 1
    return True
    
while True:
    p = int(input("\nEnter number:"))
    if p==0:
        break

    if is_prime1(p):
        print("Leman say: prime")
    else:
        print("Leman say: not prime")

    if is_prime2(p):
        print("Raben Miller say: prime")
    else:
        print("Raben Miller say: not prime")

#Prime numbers for test https://goo.gl/UdPdZc