1 
 #include<stdio.h>
 #include<time.h>

 int main()

  {

    clock_t start;
    double d;
    long int n,i,j;
    scanf("%ld",&n);
    n=100000;
    j=2;
    start=clock();
    printf("\n%ld",j);

       for(j=3;j<=n;j+=2)
       {
          for(i=3;i*i<=j;i+=2)

          if(j%i==0)
            break;

           if(i*i>j)
          printf("\n%ld",j);

        }
    d=(clock()-start)/(double)CLOCKS_PER_SEC;
    printf("\n%f",d);

}

上記のプログラムで n=100000 のとき、実行時間は 0.015 秒でした。また、C でエラトステネスのふるいアルゴリズムを実装したところ、n=100000 の実行時間は 0.046 でした。

上記のアルゴリズムは、実装した Sieve のアルゴリズムよりも高速です。

上記のプログラムの時間計算量は??

私のふるいの実装

 #define LISTSIZE 100000    //Number of integers to sieve<br>
 #include <stdio.h>
 #include <math.h>
 #include <time.h>

int main()
{   


    clock_t start;
    double d;
    long int list[LISTSIZE],i,j;
    int listMax = (int)sqrt(LISTSIZE), primeEstimate = (int)(LISTSIZE/log(LISTSIZE));

    for(int i=0; i < LISTSIZE; i++)
        list[i] = i+2;
    start=clock();

    for(i=0; i < listMax; i++)
    {
        //If the entry has been set to 0 ('removed'), skip it
        if(list[i] > 0)
        {
            //Remove all multiples of this prime
            //Starting from the next entry in the list
            //And going up in steps of size i
            for(j = i+1; j < LISTSIZE; j++)
            {
                if((list[j] % list[i]) == 0)
                    list[j] = 0;
            }
        }
    }
    d=(clock()-start)/(double)CLOCKS_PER_SEC;

    //Output the primes
    int primesFound = 0;
    for(int i=0; i < LISTSIZE; i++)
    {
        if(list[i] > 0)
        {
            primesFound++;

            printf("%ld\n", list[i]);
        }
    }
    printf("\n%f",d);
    return 0;
}
4

6 に答える 6

3

結果に影響を与える可能性のあるものがいくつかあります。確かに、ふるいの実装のコードを確認する必要があります。clockまた、あなたのコンピュータの機能の解像度は何ですか? 実装でミリ秒レベルの高度な精度が得られない場合、結果は測定誤差の範囲内に収まる可能性があります。

問題はここにあると思います：

            //Remove all multiples of this prime
            //Starting from the next entry in the list
            //And going up in steps of size i
            for(j = i+1; j < LISTSIZE; j++)
            {
                    if((list[j] % list[i]) == 0)
                            list[j] = 0;
            }

これは、素数の倍数をすべて削除するには不十分な方法です。組み込みの乗算演算子を使用して倍数を削除しないのはなぜですか? このバージョンははるかに高速です。

            //Remove all multiples of this prime
            //Starting from the next entry in the list
            //And going up in steps of size i
            for(j = list[i]; j < LISTSIZE; j+=list[i])
            {
              list[j] = 0;
            }
于 2009-08-30T07:24:46.680 に答える
1

上記のプログラムの時間計算量は??

プログラムの時間の複雑さを経験的に測定するには、複数のデータ ポイントが必要です。N の複数の値に対してプログラムを実行し、N 対時間のグラフを作成します。これは、スプレッドシート、GNUplot、または方眼紙と鉛筆を使用して行うことができます。ソフトウェアや昔ながらの数学を使用して、データに適合する多項式曲線を見つけることもできます。

非経験的: 計算の複雑さを分析することについて多くのことが書かれています (そしてコンピューター サイエンスのクラスで講義されています)。計算複雑性理論に関するウィキペディアの記事は、さらに読むためのいくつかの出発点を提供するかもしれません。

于 2009-09-01T07:43:07.720 に答える
0

これらの実行時間は小さすぎて意味がありません。システム クロックの解像度は、そのようなレベルまで正確ではありません。

正確なタイミング情報を取得するには、アルゴリズムをループで実行する必要があります。これを数千回繰り返して実行時間を少なくとも 1 秒にすると、その時間をループ回数で割ることができます。

于 2009-12-22T14:28:41.357 に答える
0

時間の複雑さのために：

~LISTMAX 回の反復の外側のループと最大の内側のループがあります。LISTSIZE 回の繰り返し。これは、あなたの複雑さが

O(sqrt(n)*n)

ここで、n = リストサイズ。内部ループは毎回カウントを減らし、不明な数値ごとにのみ実行されるため、実際には少し低くなります。しかし、それを計算するのは難しいです。O-Notation は上限を提供するため、O(sqrt(n)*n) で問題ありません。

于 2009-09-01T08:06:42.947 に答える
0

動作を予測するのは困難ですが、メモリへのアクセスは安価ではないことを考慮する必要があります...小さな素数に対して再度計算する方がおそらく高速です。

于 2009-09-01T08:14:58.967 に答える