はじめに
今日も初学者がpaizaで遊ぶ。
問題の全文は下記から確認できる。
変数名は基本的にpaiza解答例順序で、自分用に見やすくしたい部分などは変えたりしている。
問題文
今の時点でゴールドバッハ予想（「全ての 3 よりも大きな偶数は 2 つの素数の和として表すことができる。」）に反例がないことを知った paiza 君は、
自分もそれっぽい予想を言えば数学界に名を残せるのではないかと思い、正しいかもわからない次の paiza 予想を立てました。「全ての 3 よりも大きな平方数は 2 つの素数の和として表すことができる。」
この予想が正しいかどうかを検証するために、4 以上 10^8 以下の平方数（9999 個）の中に paiza 予想を満たさないものが存在するかを調べましょう。
数字大好き人間なら一度は予想を妄想するものなのだろうか、paiza君は自分では証明したくないようなので私がします。
ゴールドバッハ予想の方ついての現状の理解度は、素数なんていっぱいあるんだからフィットする組み合わせも存在するでしょという感じ(浅い)
アルゴリズムを賢くする
9999の平方数は99980001で、99980001全ての素数判定をするとタイムオーバーするんだろうなとは察する、それはそう。
これをスッキリさせるためのアルゴリズムを実際に思いついた順に書くと
①2つの素数の和が奇数の平方数は全て、2+奇数
②偶数の平方数はゴールドバッハ予想により、2つの素数の和
③判定が必要な平方数は全て奇数のため、平方数x-2の素数を判定する時の最大値は少なくとも(x-2)**0.5
実際にpaizaに提出したコード
n = 10000
def n_root_range(i):
return int((i**2-2)**0.5)
for i in range(3,n,2):
x = i**2
for j in range(3,n_root_range(i),2):
if (x-2)%j == 0:
print(x)
break
この予想が正しい場合は"paiza's conjecture is correct."を出力してね？という条件なのだが、流石に121の段階で反例が出てきたらpaiza君には「諦めてくれ」という気持ちしか出てこない。