projecteuler/Problem 060.py at master · dyhwong/projecteuler · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from math import sqrt

def isPrime(n):
    for i in range(3, int(sqrt(n)) + 1):
        if n % i == 0:
            return False
        else:
            i += 2
    return True

def concatenate(a, b):
    return int(str(a) + str(b))

def isconcatPrime(a, b):
    if isPrime(concatenate(a, b)) and isPrime(concatenate(b, a)):
        return True
    return False

def eratosthenes(n):
    sieve = [True] * n
    for x in xrange(2, int(n ** 0.5) + 1):
        for i in xrange(2*x, n, x):
            sieve[i] = False
    return sieve

def getPrimes(sieve):
    primes = []
    for i in xrange(2, len(sieve)):
        if sieve[i]:
            primes.append(i)
    return primes

def addPrime(primeList, primes):
    newList = []
    for i in xrange(primes.index(primeList[-1]) + 1, len(primes)):
        for prime in primeList:
            if not isconcatPrime(prime, primes[i]):
                break
            elif prime == primeList[-1]:
                tempList = primeList + [primes[i]]
                newList.append(tempList)
    return newList

def main():
    primes = getPrimes(eratosthenes(10000))
    newList = []
    for primeList in primes[:50]:
        newList += addPrime([primeList], primes)
    newList2 = []
    for primeList in newList:
        newList2 += addPrime(primeList, primes)
    newList = []
    for primeList in newList2:
        newList += addPrime(primeList, primes)
    newList2 = []
    for primeList in newList:
        newList2 += addPrime(primeList, primes)
    print sum(newList2[0])

main()