最速の素数判定アルゴリズム　　

じゃ、メルセンヌ素数について
2^n-1 が素数ならメルセンヌ素数
2^2-1=11b=3 2^3-1=111b=7

>>119 が書いてるように 3の倍数かどうかは２桁毎に区切って加算 7は3桁毎に加算
して判断してもいいから

2^4-1=1111b は3+3=３の倍数、 2^6-1=111111bも3と7の倍数 と即座に判るから素数ではない
つまり nがまず素数じゃないと2^n-1も素数じゃない

　Lucas-Lehmer テストは
ttp://www.nara-edu.ac.jp/~asait/prime.htm
　 X[0]=4から始まって
　X[i]=X[i-1]^2-2 という数を用意し、X[n-1] % (（2^n)-1) =0 　という簡単な方法で検査可能
　これを使ったフリーソフトで700人の仲間と高校生が記録を打ち立てた

　ところで　2^n-1に比べてX[i] は非常に大きな数になる。そこでさらに Lucasは
　途中で モジュラ計算をしてもいい事を発見した
　ttp://alfin.mine.utsunomiya-u.ac.jp/~niy/algo/l/lucas.html

Lucasテストに必要なのは　 (a^2-2)%b という計算だけ

つまりモジュラーな２乗と引算だけ用意すればいい

2^5-1 = 31でテストすると b
4 -> (4*4)-2=16-2=14
14->(14*14)%31-2=10-2=8
8->(8*8)%31-2=2-2=0

めでたくゼロになって31が素数と判ります