def main():
    summa = 0
    for num in range(1,150000001):
        arr_num = []
        arr_const = [1,3,7,9,13,27]
        
        #List to hold all possible values
        for i in arr_const:
            var = ((num**2)+i)
            if(sp.isprime(var)):
                arr_num.append(var) 
                
        count = len(arr_num)
              
        #Number of primes between two numbers
        count_prime = 0
        for k in range((num**2)+1,(num**2)+27+1):
            if(sp.isprime(k)):
                count_prime += 1
        
        if(count == 6):
            if(count == count_prime):
                print num
                summa += num
            
    print "Total : " + str(summa)

def euler58():
    cnt = 1
    prime_cnt = 0
    n = 2
    while True:
        prime_cnt += isprime(4 * n * n - 10 * n + 7)
        prime_cnt += isprime(4 * n * n - 8 * n + 5)
        prime_cnt += isprime(4 * n * n - 6 * n + 3)
        cnt += 4
        if prime_cnt * 1.0 / cnt < 0.1:
            return n * 2 + 1
        n += 1

def keycreation(p, q, e):
    n = p * q

    # check p, q are primes
    if not(isprime(p) and isprime(q)):
        raise Exception('p, q are not primes')

    # check gcd(e, (p-1)(q-1))=1
    if (gcd(e, (p-1) * (q-1)) == 1): 
        return (n, e)
    else:
        raise Exception('Improper e')

def check_trucations(n):

    number_digits = digits(n)

    for x in range(1, len(number_digits)):
        truncation1 = number_digits[x:]
        truncation2 = number_digits[:len(number_digits) - x]
        number1 = digits_to_int(truncation1)
        number2 = digits_to_int(truncation2)

        if (not sympy.isprime(number1)) or (not sympy.isprime(number2)):
            return False
    return True

def golbach_other():
    i = 7
    while True:
        i = i+2
        if isprime(i):
            continue
        max_j = int(math.sqrt(i/2))
        g = False
        for j in range(1,max_j+1):
            if isprime(i - 2*j*j):
                g = True
                break
        if not g:
            return i

def odd_composite_gen():
    """infinite generator of composite numbers"""
    x = 3
    while 1:
        x += 2
        if not isprime(x):
            yield x

def main():
    summa = 0
    for i in range(1,2000001):
        if(sp.isprime(i)):
            summa += i
            
    print summa

def verifie_paire_debug(A, B):
    """Version plus lente qui fait tous les tests, et affiche vrai ou faux pour chaque somme a + b."""
    if A is None or B is None:
        return False
    reponse = True
    for a in A:
        if not isprime(a):
            print("  - a = {:<6} est pas premier, ECHEC ...".format(a))
            reponse = False
        for b in B:
            if not isprime(a + b):
                print("  - a = {:<6} + b = {:<6} donnent {:<6} qui n'est pas premier, ECHEC ...".format(a, b, a + b))
                reponse = False
            else:
                print("  - a = {:<6} + b = {:<6} donnent {:<6} qui est bien premier, OK ...".format(a, b, a + b))
    return reponse

def quadResidue(p):
   #Check whether p is prime and odd
    if(not sp.isprime(p)):
        return "~"
    if(p%2==0):
        return "~"
    #This are the variables storing outputs
    quadR=[]
    quadNR=[]
    #Making array S with numeral count 1 to (p-1)/2
    S=[]
    #This iss the loop process for making S when a=1
    for j in range(1,int((p-1)/2)+1):
        S.append(j)
    #This operation is required for 
    #numpy based functionalities    
    S=np.array(S) 
    #Iterating for each a less than p, greater than 1   
    for a in range(1,p):
       SNew=S*a #Makes life easy, as we can make S with any a
       SNew%=p #Left reminders
       n=0 #Count of remainders greater than p/2
       #For the count of n, so to get the power
       for i in range(len(SNew)):
           if(SNew[i]>(p/2)):
               n+=1
       #Lengndre symbol operation        
       if((-1)**n==1):
           quadR.append(a)
       else:
           quadNR.append(a)
    return[quadR,quadNR]

def solve():
	for i in range(len(digits)):
		for p in permutations(digits[i:]):
			x = int(''.join(p))
			if isprime(x):
				return x
	return -1

def prove_factorial_divides_by_n_primes(n):
    ''' Always returns True because a factorial
        is divisible by the all primes below n
        by definition'''
    return all(imap(lambda x, y: x % y == 0,
                    repeat(factorial(n)),
                    [y for y in range(1, n) if isprime(y)]))

def calc_some(p):
    if p <= 5:
        raise ValueError("p must be larger than 5")
    if not sympy.isprime(p):
        raise ValueError("specify prime. actual p = {}, ntheory.divisors = {}".format(p, ntheory.divisors(p)))
    r = reciprocal(p)
    seq = calc_recurrence_seq(p)
    d = len(seq)
    former = r[:d // 2]
    latter = r[d // 2:d]
    if d % 2 == 0:
        print('length of recurrence is even')
        print('1/{} = '.format(p), r)
        print('former = ', former)
        print('latter = ', latter)
        print('former + latter =\n', Decimal(former) + Decimal(latter))
    else:
        print('length of recurrence is not even. In fact')
        print('1/{}'.format(p), r)
        print('seq = ', seq)
        print('len(seq) = ', len(seq))
        print('But you may find something')
        if latter[0] == 9:
            print("you're lucky")
            print('former = ', former)
            print('latter = ', latter)
            print('former + latter =\n', Decimal(former) + Decimal(latter))

def replaced_is_prime(n, replace):
    n = str(n)
    res = 0
    for i in range(replace, 10):
        if isprime(int(n.replace(str(replace), str(i)))):
            res += 1
    return res

def main():
    count = 0
    for i in range(0,1000000):
        if(sp.isprime(i)):
            count += 1
            if(count == 10001):
                print i
                break

def isQuadraticResidue(p, a):
    if isprime(p):
        if a ** ((p - 1) / 2) % p == 1:
            return True
        else:
            return False
    else:
        return "N not a prime"

def is_goldbach_composite(n):
    if isprime(n):
        return True
    for prime in sieve.primerange(1, n):
        for ds in double_squares(n):
            if prime + ds == n:
                return True
    return False

 def is_goldbach(n):
     """can n can be written as the sum of a prime and twice a square?"""
     for s in sq2:
         if s >= n:
             break
         if isprime(n - s):
             return True
     return False

def truncatables_primes():
    count =0
    s = 0
    last_prime = 7
    while count<11:
        prime = nextprime(last_prime)
        prime_str = str(prime)
        is_cool = True
        for i in range(1,len(prime_str)):
            p1 = int(prime_str[i:])
            p2 = int(prime_str[:-i])
            if not (isprime(p1) and isprime(p2)):
                is_cool = False
        if is_cool:
            count = count +1
            s = s+prime
        last_prime = prime
    return s

def pandigital_prime():
    max_p = 0
    for n in range(1,10):
        all_digits = [str(i) for i in range(1,n+1)]
        for perm in permutations(all_digits):
            p = int("".join(perm))
            if isprime(p):
                max_p = max(p, max_p)
    return max_p

def rand_prime(min_, max_):
    '''get a random prime between two numbers'''
    p = math.floor(random.random() * ((max_ - 1) - min_ + 1)) + min_
    if sympy.isprime(p):
        print(p, 'is prime')
        return p
    else:
        print(p, 'is not prime')
        return rand_prime(min_, max_)