【Project Euler】Problem 46: ゴールドバッハの他の予想

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 46. ゴールドバッハの他の予想

原文 Problem 46: Goldbach's other conjecture

問題の要約：以下のゴールドバッハの他の予想が成り立たない最小の奇数の合成数を求めよ

奇数の合成数は（素数$+$平方数 $\times 2$）の形で表すことができる

\begin{align}
9&=7+2 \times 1^2 \\
15&=7+2 \times 2^2 \\
21&=3+2 \times 3^2 \\
25&=7+2 \times 3^2 \\
27&=19+2 \times 2^2 \\
33&=31+2 \times 1^2 \\
\end{align}

import itertools
from sympy import primerange, isprime

def isSq(n):
  sq = n**(1/2)
  return sq == int(sq)

def isGconj(on): # check if a odd number follows Goldbach's other conjecture
  for pn in primerange(2,on):
    if isSq((on-pn)/2): return True
  return False

for on in itertools.count(9,2):    
  if isprime(on): continue     # on: Odd non prime  number
  if not isGconj(on):
    print(f"Answer is {on}")
    break

（開発環境：Google Colab）