0046 另一个猜想
* * * *
拉格朗日计划
* * * *
另一个猜想

哥德巴赫也曾经猜想,每个奇合数都可以写成一个素数与一个平方数的两倍之和,例如:

9=7+2×12 15=7+2×22 21=3+2×32 25=7+2×32 27=19+2×22 33=31+2×12 不过这个猜想最终被证明是错误的。

找出不能写成一个素数与一个平方数的两倍之和的最小奇合数。

本题难度:



解答

暴力搜索可得结果是5777

target=10000
d=[0]*target
n=2
while n < target:
    for i in range(n+n,target,n):
        d[i]=d[i]+1
    n=n+1
    while n < target and d[n]>0:
        n=n+1

primeList=[k for k in range(2,target) if d[k]==0]

squareList=[2*i*i for i in range(1,100)]

n=33
notFound=True

while notFound:
    n+=2
    while n in primeList:
        n+=2
    i=0
    while squareList[i] < n and n-squareList[i] not in primeList:
        i+=1
    notFound=squareList[i] < n

print n