project euler 46. problem

크리스티안 골드바흐는 모든 홀수인 합성수를 (소수 + 2×제곱수)로 나타낼 수 있다고 주장했습니다. 9 = 7 + 2×12 15 = 7 + 2×22 21 = 3 + 2×32 25 = 7 + 2×32 27 = 19 + 2×22 33 = 31 + 2×12 이 추측은 잘못되었음이 밝혀졌습니다. 위와 같은 방법으로 나타낼 수 없는 가장 작은 홀수 합성수는 얼마입니까?

def isPrime(target):
    i=2
    while i<target:
        if target % i == 0:
            return False
        i+=1
    return True
 
def makeOddCompositeNumbersAndPrimeNumber(start, stop):
    numbers = range(start, stop)
    compositeNumbers = numbers
 
    primeNumbers = []
    for number in numbers:
        if isPrime(number):
            compositeNumbers.remove(number)
            primeNumbers.append(number)
 
    oddCompositeNumbers = []
    for compositeNumber in compositeNumbers:
        if compositeNumber % 2 == 1:
            oddCompositeNumbers.append(compositeNumber)
    
    return oddCompositeNumbers, primeNumbers
 
def proveOpinion(targets, primeSet):
    for target in targets:
        flag = False
        for prime in primeSet:
            i = 1
            if prime < target:
                while(True):
                    opinion = prime + 2 * i ** 2
                    if opinion == target:
                        print target, " = ", prime, " + 2 x ", i, "**2" 
                        flag = True
                        break
                    elif opinion > target:
                        break
                    i+=1
            elif prime > target:
                print "prime is ", prime, " / target is ", target
                return target
 
            if flag:
                break
 
 
oddCompositeNumbers, primeNumbers =  makeOddCompositeNumbersAndPrimeNumber(3, 10000)
print proveOpinion(oddCompositeNumbers, primeNumbers)
 

 

...

5765  =  563  + 2 x  51 **2

5767  =  149  + 2 x  53 **2

5769  =  151  + 2 x  53 **2

5771  =  569  + 2 x  51 **2

5773  =  571  + 2 x  51 **2

5775  =  157  + 2 x  53 **2

prime is  5779  / target is  5777

5777