Project Euler 46

• 問題

Problem 46：Goldbach's other conjecture
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

• 解答例

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

ansList = []
num = 9
while len(ansList) < 1:
    isFound = False
    if isPrime(num):
        num += 2
        isFound = True
        continue
    i = 1
    while (num - 2 * i * i) > 0:
        if isPrime(num - 2 * i * i):
            isFound = True
            break
        i += 1
    if not isFound:
        ansList.append(num)
    num += 2

print(ansList)