C言語の高速化処理について

Question

前提・実現したいこと

C言語を用いて、１〜１０万までの数字の中から素数を見つけ出し、表示するプログラムを作りたくてググったところ、２つのソースコードが見つかりました。

発生している問題・エラーメッセージ

実行速度が全然違ったので、どうしてこんなに変わるのか教えてください！
初心者なので、出来るだけわかりやすく教えていただけると幸いです。

該当のソースコード

#include <stdio.h>

int main(void)
{
  int i,j,k;
  int c=0; 

  for(i=1;i<=100000;i++) {
    k=0;
    for(j=1;j<=i;j++)
  {
  if(i%j==0) k++;
  }

  if(k==2) {
    printf("%d ",i);
    ++c; 
  }
}

  printf("\n");

  printf("個数: %d\n",c); 

  return 0;
}

#include <stdio.h>

int dispPrimarity(int n1, int n2)
{

        int i = 0;
        int j = 0;

        // 素数判定
        for( i=n1;i<=n2;++i ) {
                int flag = 0;
                for( j=2;j<i;++j) {
                        if( i%j == 0) {
                                flag = 1;
                                break;
                        }
                }
                // 素数なら出力
                if( flag == 0 )
                        printf("%d ", i);
        }
        return 0;
}

int main(void)
{
        // 1～100000までの素数を表示
        dispPrimarity(1, 100000);

        return 0;
}

補足情報（FW/ツールのバージョンなど）

最初の方の実行速度が
real 0m18.922s
user 0m18.303s
sys 0m0.104s

２つ目の実行速度が
real 0m1.855s
user 0m1.670s
sys 0m0.016s
でした。

Answer 1

最初のほうは、合成数である場合も約数の個数を算出するために内側のループの最後まで実行しますが、2つ目は合成数と判明した時点で残りの処理を飛ばしているからです。偶数の処理がほぼ丸ごとカットされる、と言えば分かりやすいでしょうか。

Answer 2

i = 99999あたりで

k = 0;
for(j=1;j<=i;j++)
  {
    if(i%j==0) k++;
  }

int flag = 0;
for( j=2;j<i;++j) {
    if( i%j == 0) {
        flag = 1;
        break;
    }
}

それぞれのループは何回i%jを行うのかを考えるとよいでしょう。

ついでに継続条件をもう少し詰める事ができます。

int flag = 0;
for( j=2;j*j<=i;++j) {
    if( i%j == 0) {
        flag = 1;
        break;
    }
}

---

ま、エラトステネスの篩を実装した方が速いと思いますが

Answer 3

1番目の方は、外側のループ（i）で指定されている数の「約数の数」を算出して、その値が2であるかどうか（素数は1と自分自身の二つしか約数を持たない）で判断しています。

2番目の方は外側のループは同じですが、「2以上で、その数を割りきることができたら合成数と判断して処理を打ち切る」のです。

例えば i が 10000 のときを考えると、内側のループが 10000 回と1回（2で割り切れるのでそこで打ち切り）というくらい違ってきます。

Comments

[shun011]

１番わかりやすかったです！！細かくありがとうございます！！