// gist.github.com d.hatena.ne.jp このブログを参考に書きました. とても参考になりました. 再帰のイメージを書いて見た. (limit = 1000) pで割り切れなくてもn//pでnを小さくしていけば結局同じなんですね.

type 以下の素数のリストをエラトステネスの篩で作る. その素数のみの積で表される数のうちlimit = 10**9を超えない数を数え上げれば良い. もっとも小さい素数は2であり2**n で始めてlimit を越えるのはn = 30であるので, 素数のリストから30個重複を許さな…

滅茶苦茶汚いコードだし理論もクソだったのでコードは載せない. 考え方は10<= n <= 150000000まで回してその一つ一つにn^2+1, ..., n^2+27を計算しそれぞれをMR法で素数か判定する. この時全体の時間を考えるとMR法で生成する乱数は少ない方が良い. 3回もや…

nが素数かを判定するプログラムです. フェルマーの小定理に基いて出来ています. フェルマーの小定理は a,n が互いに素のとき 「nが素数 → a^(n-1) modn = 1」 というものです. 対偶をとって 「a^(n-1) modn !=l 1 → nが素数でない(合成数)」 プログラムで書…