Christian Goldbach predicted that all odd composite numbers could be represented by twice the square number and the sum of the prime numbers.
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
Later, this conjecture turned out to be false.
What is the smallest odd composite number that cannot be represented by the sum of twice a square number and a prime number? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2046
It was determined whether or not the composite number was a prime number obtained by subtracting twice the square number.
Click here for mymath. https://github.com/cof01/ProjectEuler/blob/master/mymath.py
# coding: utf-8
import math
from mymath import get_primes, is_prime
def main():
MAX=10**6
pri = get_primes(MAX)
sq_list = [i*i*2 for i in range(int((MAX**0.5)/2)+1)]
ans = 0
for odd in range(9,MAX,2):
if is_prime(odd, pri):
continue
SumOfPrimeAndTwiceSquare = True
for sq in sq_list:
if sq >= odd:
break
if is_prime(odd - sq, pri):
SumOfPrimeAndTwiceSquare = False
break
if SumOfPrimeAndTwiceSquare:
ans = odd
break
print ans
main()
Recommended Posts