今までに見つけた中で一番大きな素数は、2000万桁を超えるものらしい。
素数は無限にあるわけですが。。それにしても2000万桁ってすごいよね。
ちなみに素数ではない数は、合成数というそうな。
習ったんかもしれんが、忘れてるねぇ。
エラトステネスのふるいを使って、素数を求めるサンプル
エラトステネスのふるいを使って、素数を求めます。
とりあえず50までの範囲で。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | import java.util.ArrayList; import java.util.List; public class EratosthenesTest { public static void main(String[] args) { //素数を求める範囲（最大） int max = 50; //素数を求める範囲で、0,1を除いてtrueのリストを作成 List<Boolean> primeList = new ArrayList<Boolean>(); for(int i=0 ; i<max+1 ; i++) { if(i<2) { primeList.add(false); }else { primeList.add(true); } } //二乗して最大値までの範囲内で、素数の可能性があるものを対象に.. for(int i=2 ; i*i<=max ; i++) { if(primeList.get(i)) { //倍数を振り落とす for(int j=i*i; j<=max ; j+=i) { primeList.set(j, false); } } } //素数を出力 for(int i=2; i<=max ; i++) { if (primeList.get(i)) { System.out.print(i + ","); } } } } |
実行結果
1 | 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47, |
サンプルの解説
エラトステネスのふるいは、素数を求めるアルゴリズムです。
maxの値を変えれば、素数を調べる範囲を変えられます。
二乗が調べるしきい値になっているのがポイントで、調べる数の二乗以下は調べていません。
例えば、5の倍数でふるいにかけるときで考えると、5 x 5 = 25の二乗以下はこれら。
- 5 x 2 = 10
- 5 x 3 = 15
- 5 x 4 = 20
これらの数字は、2,3,(4=2×2)の倍数でもあるので、既にチェック済み。
エラトステネスのふるいは、昇順に倍数を調べていくので、これらは調べなくて良い。ということです。
おもしろいですよね。
ちなみに、wikipediaに素数を覚えるための語呂合わせが載ってましたｗ
誰が考えたんかな。比較的新しそうだけど。。
