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)
コメント