#!/usr/bin/python -OO

import random
import array
import math


def make_prime(min_digits=100, max_digits=None):
    if max_digits is None:
        max_digits = min_digits + 1
    while True:
        i = random.randrange(10 ** min_digits, 10 ** max_digits)
        if miller_rabin(i):
            return i

# 20 iterations gives us a 9.09e-11% chance of a strong liar
def miller_rabin(cand, tests=20):
    if cand is 2:
        return True
    #No even numbers allowed
    if cand < 2 or not cand & 1:
        return False

    d = n1 = cand - 1
    # factor powers of two from d
    while not d & 1:
        d >>= 1
        
    for i in xrange(tests):
        a = random.randrange(0, cand - 2) + 1
        t = d
        y = mod_mul(a, t, cand)
        while t != n1 and y not in (1, n1):
            y = (y * y % cand)
            t <<= 1
                
        if y != n1 and ~t & 1:
           return False
            
    return True
         

def mod_mul(base, power, mod):
    r = 1
    while power:
        if power & 1:
            r = (r * base % mod)
        base = (base * base % mod)
        power >>= 1        
    return r

def eratosthenes(max):
    r = array.array('L', [0,0,1])
    
    for i in xrange(2,max):
        r.append(1)
        
    # Skip 0, 1
    e = enumerate(r)
    e.next()
    e.next()
    for i,j in e:
        if j:
            for k in range(i<<1, max+1,i):
                r[k] = 0
    return [i for i,j in enumerate(r) if j]

# pi(x) approximates the number of primes less than x
def pi(max):
    return long(max / math.log(max - 1))

if __name__ == '__main__':
    for i in range(10): print make_prime()