Christian Goldbach a prédit que tous les composites impairs pourraient être représentés par la somme des carrés et des nombres premiers.
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
Plus tard, cette conjecture s'est avérée fausse.
Quel est le plus petit nombre impair de composition qui ne peut pas être représenté par la somme du double du nombre carré et du nombre premier? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2046
Il a été déterminé si le nombre obtenu en soustrayant deux fois le nombre carré était un nombre premier.
Cliquez ici pour 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