掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.28262

100万番目の素数を求めるプログラムを高速化
投稿者---A(2006/09/28 10:29:09)


C言語を始めたばかりの初心者です。
100万番目の素数を求めたくて、プログラムを作成して、一応結果は出せたようなのですが、もっと大幅に計算時間を短縮したいと思っています。
過去ログを探してみたところ、100番目までとか1000番目までとかのプログラムは見つけることができたのですが、100万番目となると、時間がかかりすぎるので困っています。
以下のように、素数の定義に基づいて除算を繰り返していくプログラムを書いたのですが、これで約10分かかりました。
ネットで調べたらAKS素数判定法だとか難しそうな方法があったのですが、1分くらいで計算しようと思ったらこういう特殊な方法を使うしかないのでしょうか?アドバイスをお願いいたします。

/*
    #include<stdio.h>
#include<math.h>
int main(void){
    int a;
    int b=0;
    int c=0;
    int m;
    int n;
    int p[8]={4,2,4,2,4,6,2,6};
    
    printf("Input a natural number:");
    scanf("%d",&a);
    if(a==1){printf("\nThe 1st prime number is 2");}
    if(a>=2){printf("2  ");c++;}
    if(a>=3){printf("3  ");c++;}
    if(a>=5){printf("5  ");c++;}
    for(m=7;;b++){
        for(n=7;n<=sqrt(m);n+=2){
        if((m%n)==0) break;}
        if(n>sqrt(m)){printf("%d  ",m);c++;}
        if(c==a)break;
        m+=p[b%8];
    }
    printf("\nThe %dth prime number is %d",c,m);
    return 0;
}




この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:100万番目の素数を求めるプログラムを高速化 28263 nano 2006/09/28 11:21:49
<子記事> Re:100万番目の素数を求めるプログラムを高速化 28265 たかぎ 2006/09/28 11:37:33
<子記事> Re:100万番目の素数を求めるプログラムを高速化 28267 かずま 2006/09/28 13:51:03
<子記事> Re:100万番目の素数を求めるプログラムを高速化 28277 A 2006/09/29 12:16:20


No.28263

Re:100万番目の素数を求めるプログラムを高速化
投稿者---nano(2006/09/28 11:21:49)


sqrt関数を使わないようにするだけで、
けっこう高速化できると思います。

        for(n=7;n*n<=m;n+=2){
        if((m%n)==0) break;}
        if(n*n>m){printf("%d  ",m);c++;}




この投稿にコメントする

削除パスワード

No.28264

Re:100万番目の素数を求めるプログラムを高速化
投稿者---nano(2006/09/28 11:26:11)


あと、途中経過の出力はどうしても必要ですか?
        if(n*n>m){printf("%d  ",m);c++;}

このprintfによる出力が、実行時間にかなり影響していそうです。


この投稿にコメントする

削除パスワード

No.28265

Re:100万番目の素数を求めるプログラムを高速化
投稿者---たかぎ(2006/09/28 11:37:33)
http://takagi.in/


ちょっと高速化してみました。(見辛かったので、インデントも変えています)
#include<stdio.h>
#include<math.h>

int main(void)
{
    int a;
    unsigned int b = 0;
    int c = 0;
    unsigned int m;
    unsigned int n;
    unsigned int p[8] = { 4, 2, 4, 2, 4, 6, 2, 6 };

    printf("Input a natural number:");
    scanf("%d", &a);
    if (a == 1) {
        printf("\nThe 1st prime number is 2");
    }
    if (a >= 2) {
        c++;
    }
    if (a >= 3) {
        c++;
    }
    if (a >= 5) {
        c++;
    }
    for (m = 7;; b++) {
        unsigned int sqrtm = sqrt(m);
        for (n = 7; n <= sqrtm; n += 2) {
            if ((m % n) == 0)
                break;
        }
        if (n > sqrtm) {
            c++;
        }
        if (c == a)
            break;
        m += p[b % 8];
    }
    printf("\nThe %dth prime number is %d", c, m);
    return 0;
}

途中経過の出力をやめて、sqrtの計算を一箇所にまとめただけで、(環境にもよりますが)4倍近く高速化できました。
あとは、変数をunsigned intにすることで、コンパイラが最適化しやすいようにしています。



この投稿にコメントする

削除パスワード

No.28267

Re:100万番目の素数を求めるプログラムを高速化
投稿者---かずま(2006/09/28 13:51:03)


素数を順番に求めているのだから、それで割ってみれば速くなるのでは?
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define N  4000

int main(void)
{
    int a, b, c, m, n, s;
    static int z[N] = { 0, 2, 3, 5, 7, };
    static int p[8] = { 4, 2, 4, 2, 4, 6, 2, 6 };
    clock_t t;

    while (printf("Input a natural number: "), scanf("%d", &a) == 1) {
        if (a == 1) { printf("The 1st prime number is 2\n"); continue; }
        if (a == 2) { printf("The 2nd prime number is 3\n"); continue; }
        if (a == 3) { printf("The 3rd prime number is 5\n"); continue; }
        t = clock();
        for (b = 0, c = 3, m = 7; ; b++) {
            s = sqrt(m);
            for (n = 4; n < N && z[n] <= s && m % z[n]; n++) ;
            if (n >= N) puts("out of memory"), exit(1);
            if (z[n] > s) {
                if (++c < N) z[c] = m;
                if (c == a) break;
            }
            m += p[b & 7];
        }
        printf("The %dth prime number is %d [%.3f sec]\n", c, m,
                (double)(clock() - t) / CLOCKS_PER_SEC);
    }
    return 0;
}



この投稿にコメントする

削除パスワード

No.28268

Re:100万番目の素数を求めるプログラムを高速化
投稿者---かずま(2006/09/28 14:53:41)


> #define N  4000

100万番目だったら、N は 600 程度で十分です。

また、他の方の指摘どおり、sqrt を使わないようにしたり、int を unsigned
に変えると、もっと速くなります。

int --> unsigned

s = sqrt(m); を削除。
for (... z[n] <= s  -->  for (... z[n]*z[n] <= m
if (z[n] > s) {     -->  if (z[n]*z[n] > m) {



この投稿にコメントする

削除パスワード

No.28276

Re:100万番目の素数を求めるプログラムを高速化
投稿者---かずま(2006/09/29 11:38:38)


平方数も憶えておくようにしてみました。
#include <stdio.h>
#include <time.h>

#define N  600

int main(void)
{
    unsigned a, b, c, m, n;
    static unsigned p[8] = { 4, 2, 4, 2, 4, 6, 2, 6 };
    static unsigned z[N] = { 0, 2, 3, 5, 7, };
    static unsigned z2[N] = { 0, 4, 9, 25, 49, };
    clock_t t;

    while (printf("Input a natural number: "), scanf("%u", &a) == 1) {
        if (a == 1) { printf("The 1st prime number is 2\n"); continue; }
        if (a == 2) { printf("The 2nd prime number is 3\n"); continue; }
        if (a == 3) { printf("The 3rd prime number is 5\n"); continue; }
        t = clock();
        for (b = 0, c = 3, m = 7; ; b++) {
            for (n = 4; n < N && z2[n] <= m && m % z[n]; n++) ;
            if (n >= N) { puts("out of memory"); return 1; }
            if (z2[n] > m) {
                if (++c < N) z[c] = m, z2[c] = m*m;
                if (c == a) break;
            }
            m += p[b & 7];
        }
        printf("The %uth prime number is %u [%.3f sec]\n", c, m,
                (double)(clock() - t) / CLOCKS_PER_SEC);
    }
    return 0;
}



この投稿にコメントする

削除パスワード

No.28277

Re:100万番目の素数を求めるプログラムを高速化
投稿者---A(2006/09/29 12:16:20)


nanoさん、たかぎさん、かずまさん、どうもありがとうございます!
今まで簡単なものしかやったことがなくて計算量の多いプログラムは初めてだったので、勉強になりました。教えていただいたことを1つづつ試してみましたが、少しの工夫でかなり時間が変わるんですね。本当にありがとうございました。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧