2以外の素数は4n±1で表わされる。
一瞬、おっ!?と思いますが、単に奇数の事です。
では少しひねって…
5以上の素数は6n±1で表わされる。
2と3の倍数を取り除いた形です。
紛らわしいので、マイナスを取り除いて以下のように書くことにしましょう。
5以上の素数は6n＋[1,5]で表わされる。
さらに調子に乗って…。
7以上の素数は30n＋[1,7,11,13,17,19,23,29]で表わされる。
2,3だけでなく、5の倍数も取り除いてみました。
これが何の役に立つかというと
ある数が素数かどうかを判定するとき、どうするか、って話です
素数といえば、エラトステネスのふるいなんですけど、
特定の値さえ素数かどうかわかればいい状況だった時、
エラトステネスのふるいは若干コストが大きすぎると思うわけです。
で、その求め方といえば…
2以上の整数で片っぱしから割って余りが0でないか確かめる！です。
原始的な方法ですけど、確実です。
とはいっても、多少の効率化はできそうです。
2以上の整数と言ってもすべての整数で割る必要はありません。
例えば、2で割って対象の値が奇数というのがわかれば、
4,6,8という偶数で割って確かめる必要はないわけです。
それが冒頭に出てきた話になります。
2,3,5で割った後は、30n＋[1,7,11,13,17,19,23,29]の形をしている
整数のみで確認してやれば、すべての整数で割るより多少早いです。
2,3,5だけでなく、7の倍数も取り除いて…さらに11の倍数も取り除いて…
そうすると若干ながら速くなりますが、その分メモリ消費も増えます。
例えば、2,3の倍数を取り除いた形から、5の倍数も取り除くと
1/5の数値が取り除かれますが、
いったん数値を5倍して計算しているのでメモリ消費は4倍になっています。
まとめると、nという倍数を取り除くと、メモリ消費は(n-1)倍になり、
速度はn/(n-1)だけ早くなります。
大体、2～11で480個であり、この辺が閾値でしょう。
なお、2～13だと5760個になります。
32bitに限れば、65535以下の素数で割ってやればよく
65535以下では6542個の素数の素数があるので、
2～13を採用するなら、エラトステネスのふるいを使って
事前にすべての素数を求めておいた方が2倍ほどの速度向上になります。