Project Euler 49

• 問題

Problem 49：Prime permutations
The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

• 解答例

def sieveEratosthenes(num):
    isPrime = [True] * (num + 1)
    isPrime[0] = False
    isPrime[1] = False
    primes = []
    for i in range(2, (num + 1)):
        if isPrime[i]:
            primes.append(i)
            for j in range(2 * i, (num + 1), i):
                isPrime[j] = False
    return primes
    
def isPrime(num):
    if num <= 1:
        return False
    elif num == 2 or num == 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    if not(num % 6 == 1) and not(num % 6 == 5):
        return False
    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return False
        i += 6
    return True

prime1 = sieveEratosthenes(1000)
prime2 = sieveEratosthenes(10000)
prime = sorted(list(set(prime2) - set(prime1)))

for p in prime:
    for d in range(1, (9999 - p) // 2 + 1):
        if isPrime(p + d) and isPrime(p + 2 * d):
            temp = []
            list1 = sorted(list(str(p)))
            list2 = sorted(list(str(p + d)))
            list3 = sorted(list(str(p + 2 * d)))
            if list1 == list2 and list2 == list3:
                print(str(p) + str(p + d) + str(p + 2 * d))