素数を求める
素数を求めるプログラムを考えてみた。
まず素数とはどのように定義されているか確認した。
1 と自分自身以外に正の約数を持たない、1 でない自然数のことである。
ということは、1 より大きくて自分自身でないと割り切れない自然数であるってことかな。
完全に総当たり方式でいけば楽勝ですね。
でも、2 より大きな偶数は 2 で割り切れるから除外すればいいし、
ターゲット n が合成数（素数でない数）の場合、n=ab となる自然数 a , b が存在する。
a と b を掛けると、n になるのだから、a , b のうちどちらかは n の平方根以下であり、どちらかは n の平方根以上だ。
従って、素数でないかどうかを確認するには、nの平方根以下の自然数で割り切れるかどうか調べればいいはず。
これらの特徴をふまえた上で、 3 億までの素数を求めるプログラムをくんでみた。
| jp\yucchi\primenumber_loop\PrimeNumber_Loop.java |
|
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 |
package jp.yucchi.primenumber_loop; public class PrimeNumber_Loop { private static final long TARGET_NUMBER = 300_000_000L; public static void main(String[] args) { long startTime = System.nanoTime(); long n, i, primeCounter = 0L; for (n = 2L; n <= TARGET_NUMBER; n++) { // 2 より大きな偶数は処理をスキップ if ((n & 0b1) == 0 && n > 2) { continue; } for (i = (long) Math.sqrt(n); n % i != 0; i--) { // n を割り切る i を見つけ出す処理 } if (i == 1) { // n を割り切れず i が 1 の場合は素数と判定 primeCounter++; System.out.println(n + " is Prime Number." + " ---> " + primeCounter); } } System.out.println(primeCounter + "個の素数を検出しました。"); long time = System.nanoTime() - startTime; System.out.println((int) (time * 1e-9) / 3_600 + "時間" + (int) ((time * 1e-9) / 60) % 60 + "分" + (int) (time * 1e-9 % 60) + "秒" + Double.toString((time * 1e-9 % 60) % 1).substring(2)); } } |
このプログラムを実行結果は次のようになった。
2 is Prime Number. —> 1
3 is Prime Number. —> 2
5 is Prime Number. —> 3
7 is Prime Number. —> 4
11 is Prime Number. —> 5
13 is Prime Number. —> 6
17 is Prime Number. —> 7
19 is Prime Number. —> 8
23 is Prime Number. —> 9
29 is Prime Number. —> 10
299999771 is Prime Number. —> 16252316
299999801 is Prime Number. —> 16252317
299999807 is Prime Number. —> 16252318
299999813 is Prime Number. —> 16252319
299999827 is Prime Number. —> 16252320
299999897 is Prime Number. —> 16252321
299999923 is Prime Number. —> 16252322
299999939 is Prime Number. —> 16252323
299999957 is Prime Number. —> 16252324
299999977 is Prime Number. —> 16252325
16252325個の素数を検出しました。
4時間29分24秒10574628300128097
凄く時間がかかった（×_×）
ちなみに Dual Xeon 3GHz で総コア数 8 です。
ハイパースレッドは無い古い CPU です。
ちょっとでも時間短縮する為に次回は並列処理をさせてみたいと思います。
実は並列処理の方法は java.util.concurrent パッケージについて調べていた時にあるサイトに
サンプルプログラムとしてありました。
それをちょっとだけ変更して使用させていただきます。
と言いつつ睡魔に襲われてきたのでまた今度ってことにします。
それでは、つづきは Web で！
おやすみ～～～～( ^.^)( -.-)( _ _)
TAGS: Java | 2012年6月24日11:55 PM
Trackback URL