円周率で最初に見つかる10桁の素数を見つける

ksnctfを少しずつやっている。

G00913

FLAG_Q20_{first 10-digit prime found in consecutive digits of π}

とだけある。円周率の中の連続した数字のうち最初の10桁の素数を求めろということか。

円周率とか桁数無限やん。深く潜ったら時間かかりそう。

arctanを使って円周率を求めたりできるらしい。 ガウスの公式

pi/4 = 12*arctan(1/18) + 8*arctan(1/57) - 5*arctan(1/239)

がある。

参考: http://www.kurims.kyoto-u.ac.jp/%7Eooura/pi04.pdf

円周率を数列として扱えばいい。

円周率の部分的整数化が面倒なので、結局、インターネットの海から円周率をいただいた。

あとはミラー・ラビン素数判定法で楽勝。意外と深くなかった。100桁目とかにはならない模様。

以前書いた素数判定: prime_test.py(gist)

コメント

タイトルとURLをコピーしました