ゆっちのBlog

2012年 6月

素数を求める vol.2

Java

昨日、素数を求めるプログラムを作ったが 3 億までの素数を求めるのに約 4 時間半かかった。

これが速いのか遅いのかは置いといて、もう少し処理時間の短縮をはかりたい。

最近の PC はマルチコアプロセッサを搭載しているので並列処理させれば処理時間短縮が可能かもしれない。

幸いにも私の PC は 8 コアなので早速試してみました。

ちなみに下記プログラムは、java.util.concurrent パッケージについて調べていた時にあるサイトにあった

サンプルプログラムを参考にさせていただきました。

jp\yucchi\primenumber\PrimeNumber.java

package jp.yucchi.primenumber;

import java.lang.management.ManagementFactory;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.*;
import java.util.logging.Level;
import java.util.logging.Logger;

public class PrimeNumber implements Callable<List<Long>> {

    private static final long TARGET_NUMBER = 300_000_000L; // 8 の倍数を指定すること(；´Д｀)
    private final long from;
    private final long to;

    public PrimeNumber(final long from, final long to) {
        this.from = from;
        this.to = to;
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        long primeCounter = 0L;
        final int procs = ManagementFactory.getOperatingSystemMXBean().getAvailableProcessors();
        ExecutorService executor = Executors.newFixedThreadPool(procs);
        final long range = TARGET_NUMBER / procs;
        List<Future<List<Long>>> futures = new ArrayList<>();
        for (int i = 0; i < procs; i++) {
            final long from = i * range + 1;
            final long to = (i + 1) * range;
            futures.add(executor.submit(new PrimeNumber(from, to)));
        }
        executor.shutdown();
        List<Long> totalPrimes = new ArrayList<>();
        for (Future<List<Long>> future : futures) {
            try {
                List<Long> primes = future.get();
                totalPrimes.addAll(primes);
            } catch (InterruptedException | ExecutionException ex) {
                Logger.getLogger(PrimeNumber.class.getName()).log(Level.SEVERE, null, ex);
            }
        }
        for (Long prime : totalPrimes) {
            primeCounter++;
            System.out.println(prime + " 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));
    }

    @Override
    public List<Long> call() throws Exception {
        List<Long> primes = new ArrayList<>();
        for (long i = from; i < to + 1L; i++) {
            // 2 より大きな偶数は処理をスキップ
            if ((i & 0b1) == 0 && i > 0b10L) {
                continue;
            }
            long j;
            for (j = (long) Math.sqrt(i); i % j != 0; j--) {
                // i を割り切る j を見つけ出す処理
            }
            // i を割り切れず j が 1 の場合素数と判定、ただし i が 1 の場合は除く        
            if (j == 1L && i != 1L) {
                primes.add(i);
            }
        }
        return primes;
    }
}

package jp.yucchi.primenumber;

import java.lang.management.ManagementFactory;

import java.util.ArrayList;

import java.util.List;

import java.util.concurrent.*;

import java.util.logging.Level;

import java.util.logging.Logger;

public class PrimeNumber implements Callable<List<Long>> {

private static final long TARGET_NUMBER = 300_000_000L; // 8 の倍数を指定すること(；´Д｀)

private final long from;

private final long to;

public PrimeNumber(final long from, final long to) {

this.from = from;

this.to = to;

}

public static void main(String[] args) {

long startTime = System.nanoTime();

long primeCounter = 0L;

final int procs = ManagementFactory.getOperatingSystemMXBean().getAvailableProcessors();

ExecutorService executor = Executors.newFixedThreadPool(procs);

final long range = TARGET_NUMBER / procs;

List<Future<List<Long>>> futures = new ArrayList<>();

for (int i = 0; i < procs; i++) {

final long from = i * range + 1;

final long to = (i + 1) * range;

futures.add(executor.submit(new PrimeNumber(from, to)));

}

executor.shutdown();

List<Long> totalPrimes = new ArrayList<>();

for (Future<List<Long>> future : futures) {

try {

List<Long> primes = future.get();

totalPrimes.addAll(primes);

} catch (InterruptedException | ExecutionException ex) {

Logger.getLogger(PrimeNumber.class.getName()).log(Level.SEVERE, null, ex);

}

for (Long prime : totalPrimes) {

primeCounter++;

System.out.println(prime + " 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));

}

@Override

public List<Long> call() throws Exception {

List<Long> primes = new ArrayList<>();

for (long i = from; i < to + 1L; i++) {

// 2 より大きな偶数は処理をスキップ

if ((i & 0b1) == 0 && i > 0b10L) {

continue;

}

long j;

for (j = (long) Math.sqrt(i); i % j != 0; j--) {

// i を割り切る j を見つけ出す処理

}

// i を割り切れず j が 1 の場合素数と判定、ただし i が 1 の場合は除く

if (j == 1L && i != 1L) {

primes.add(i);

}

return primes;

}

このプログラムの実行結果は次のようになった。

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

　　　　略

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個の素数を検出しました。
1時間26分23秒42106727300051716

なんと 3 時間も処理時間が短縮できました。(^_^)v

それでも 1 時間半近くかかります。

こんなものなのかなぁ・・・？

素数を求めるアルゴリズムにエラトステネスの篩ってのがあります。

それも試してみましょう。

それでは

おっとそろそろ時間が・・・

~~続きは Web で！~~

つづきはまた今度ね♪

Hatena タグ: Java

TAGS: Java | 2012年6月25日8:15 AM | Comment : 0

素数を求める

Java

素数を求めるプログラムを考えてみた。

まず素数とはどのように定義されているか確認した。

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

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));
    }
}

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));

}

このプログラムを実行結果は次のようになった。

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 で！~~

おやすみ～～～～( ^.^)( -.-)( _ _)

Hatena タグ: Java

TAGS: Java | 2012年6月24日11:55 PM | Comment : 0

トヨタ博物館に行ってきた

Motor

今日は愛知県にあるトヨタ博物館までドライブに行ってきた。

とても綺麗な建物でさらに優しくて綺麗なお姉さんがいてとても幸せな時間を過ごしました。

おっと、間違った！

家族と一緒に歴史に名を刻んだ名車を見て、レストランで美味しい食事をして有意義な一日となった。

館内は写真撮影可能だということで何枚か撮ってきました。

ちょっとだけですが画像を載せておきます。

言わずと知れた名車　ボンドカーに採用された TOYOTA 2000GT

次は可愛らしい車で２気筒の水平対向エンジンを積んだ TOYOTA 800

水平対向エンジンで FR パッケージとしては TOYOTA 86 と兄弟と言ってもいいだろう。

次は HONDA の可愛らしい車です。S500

さて、次は外車です。Benz 300SL クーペ

博物館には古き時代のアメリカギャング映画に出てくるような車も多数展示されてました。

私はその時代の車はまったく解らないので昔はこんなのが走っていたのか程度にしか感動がありませんでした。(^_^;)

懐かしい車や子供の頃にプラモデルで組み立てた車もありました。

思わずこの車何処の販売店に行けば買えるの？って聞いてみたくなりました。

たとえ売ってくれるとしてもとんでもない金額を提示されるだろうからあきらめました。(..;)

しかし、お土産に TOYOTA 86 のミニカーをGET！

しかも欲しかったオレンジです。

現品限りとなっていたので速攻で購入しました。

それがこれです。

トミカのミニカーより大きくて細部まで丁寧に再現されてます。

アンテナも付いてますし、特徴あるドアミラーのカラーリングまで再現されてます。

しかもシャコタンです。

私の車高調で保安基準いっぱいまで下げた 86 より低いです(>_<)

今日はこれを枕元に置いて寝よう（爆睡

Hatena タグ: Motor

TAGS: Motor | 2012年6月24日8:33 PM | Comment : 0

TYOTA 86 のミニカー

Motor

TOTOTA 86 のトミカ製のミニカーを手に入れたので画像をアップします。

初回特別カラーのシルバーと赤の２台です。

作りはだいたい他のものと変わりはなさそうです。

ミニカー買ったのは久しぶりです。

何故か子供の頃と同じようにうれしく感じます。(*^_^*)

ついでに本物の TOYOTA 86 を買った時におまけにもらったプラスチックモデルも

ちゃんとメタリックになってますね。

グレードはトミカは GT Limited のようだけどこれは GT のようですね。

そう言えば、タミヤからプラモデルも発売されてますね。

買おうと思ったけど組み立てる時間が無いので止めました。(￣。￣;)

今日はミニカーを枕元に置いて寝るか。

子供の頃はよくそうして大人になったらいっぱい車買って乗り回すのが夢だったなぁ・・・

いっぱい車を買うことはできなかったけど車で楽しい思い出を少しずつでも増やせたらいいと思う。

Hatena タグ: Motor

TAGS: Motor | 2012年6月23日7:38 PM | Comment : 0

TRD パーツ取り付け完了

Motor

86 の　TRD パーツの取り付け完了しました。

足回りと車体パーツです。

とても良くなりました。（＾＾）

乗りごごちはもともと良いとは言えない設定の車なので聞かないでね。

さて、ボディについた傷については深く入っていて補修すると１０数万円かかるとのことでした。(>_<)

このお金があれば機械式のデフ入れられるのになぁ・・・

どうしたものか・・・

とりあえずトミカのミニカー手にいれたので後で画像をアップする予定です。

Hatena タグ: Motor

TAGS: Motor | 2012年6月23日5:34 PM | Comment : 0

« 古い記事

素数を求める vol.2

素数を求める

トヨタ博物館に行ってきた

TYOTA 86 のミニカー

TRD パーツ取り付け完了

Recent Comments

Java

NetBeans

カテゴリー

アーカイブ

RSS FEED

ねこび～ん

メタ情報

ゆっちのカレンダー

2012年6月
月	火	水	木	金	土	日
« 5月				7月 »
				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

ゆっちのBlog

素数を求める vol.2

素数を求める

トヨタ博物館に行ってきた

TYOTA 86 のミニカー

TRD パーツ取り付け完了

Popular post ranking

Recent Comments

Java

NetBeans

カテゴリー

アーカイブ

RSS FEED

ねこび～ん

メタ情報

ゆっちのカレンダー