5

私のコードを以下に貼り付けます。このプログラムを実行すると、計算が続行されます。古い Turbo C++ コンパイラを使用しています。このようなプログラムの実行にはどのくらいの時間がかかりますか?5 分ほど待ったが、何も出力されませんでした。

/*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.
*/
#include<stdio.h>
#include<conio.h>
#define TWO_MILLION 2*1000*1000
int IsPrime(long unsigned int num);
int main()
{
    long unsigned int i,sum=0;
    clrscr();
    for(i=2;i<TWO_MILLION;i++)
    {
        if(IsPrime(i))
        sum+=i;
    }
    gotoxy(25,25);
    printf("%ld",sum);
    getch();
    return 0;
}
int IsPrime(long unsigned int num)
{
    int flag=1;
    long unsigned int i;
    for(i=2;i<num;i++)
    {
        if(num%i==0)
        {
            flag=0;
            break;
        }
    }
    return flag;
}
4

10 に答える 10

21

あなたは何百万もの計算をしているのではなく、何兆もの計算をしているのです。

IsPrimeはO（n）時間で実行されます。つまり、その単一の数値を判別するためだけに200万の命令を実行します。そのようなことを200万時間行うのは時間がかかりすぎるでしょう。

これを行うには、http： //en.wikipedia.org/wiki/Sieve_of_Eratosthenesのようなものを使用する必要があります。これにより、特定の範囲のすべての素数をより効率的に決定できます。

于 2010-10-04T02:44:39.350 に答える
3

他の人が言っているように、それは長い時間がかかります。代替の興味深いアプローチの1つは、エラトステネスのふるいです。あなたはそれについて読むことができます：

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

基本的に、2...2百万という数字で配列を初期化します。まだ処理されていない最小の数は素数です。次に、この数の倍数をすべて配列から削除して続行します。それはあなたが持っているものよりもはるかに速く実行されます。

于 2010-10-04T02:48:33.870 に答える
3

風変わりな答え

gotoxy(25,25);

プログラムをテキストモードで実行していますか？テキスト画面がのみ80 x 25で、25行目が他の何かによって遮られている場合は、テキスト画面に変化が見られない可能性があります。

于 2010-10-04T02:52:00.180 に答える
3

そのようなプログラムの実行にかかる時間はどれくらいですか?

それはあなたのプラットフォームに完全に依存します。~(200 万)^2 回 (~4 兆回) の計算を実行しているので、非常に長い時間がかかるのではないかと思います。

あなたがしていることを実行するためのはるかに良い方法があります.たとえば、素数をチェックするには、数自体までではなく、数の平方根までチェックするだけで済みます。言うまでもなく、おそらくそれよりもはるかに高速に実行できる動的プログラミング ソリューションがあります。

于 2010-10-04T02:40:17.137 に答える
2

他の人が言ったように：実装の制限を確認してください

TurboC++<limits.h> がある場合、それらの実装制限には、そのヘッダーで定義された対応するマクロがあります。

#include <limits.h>
#include <stdio.h>
int main(void) {
    printf("int goes from %d to %d.\n", INT_MIN, INT_MAX);
    printf("long goes from %ld to %ld.\n", LONG_MIN, LONG_MAX);
    return 0;
}

それが失敗した場合は、制限を自分で「計算」する必要があります。オーバーフローの問題がなく、上限を「計算」するだけでよいため、に切り替えてunsignedいます（下限は0です）

#include <stdio.h>
int main(void) {
    unsigned u;
    unsigned long lu;

    u = -1; lu = -1;
    printf("unsigned ints go all the way to %u\n", u);
    printf("unsigned longs go all the way to %lu\n", lu);
    return 0;
}

私のシステムでは、最初のプログラムが出力します

int は -2147483648 から 2147483647 になります。
-9223372036854775808 から 9223372036854775807 まで長いです。

そして2番目のプログラム出力

unsigned int は 4294967295 まで
unsigned long は 18446744073709551615 まで
于 2010-10-04T08:20:02.623 に答える
2

「エピック」以外の定数に関するコメント/回答はまだありません...

#define TWO_MILLION 2*1000*1000

これは悪いです。後で値を変更すると、name-content-mismatch が発生します。

#define TWO_MILLION 5*1000*1000

または、名前を変更します

#define FIVE_MILLION 5*1000*1000

使用したすべての場所で変更する必要があります。コンテンツにちなんで定数に名前を付けないでください。これは、マジック ナンバーをマジック ネームに変えるだけです。意味にちなんで名前を付けてくださいMAX_NUMBER UPPER_LIMIT RANGE_TO_TEST。

于 2010-10-04T08:56:17.753 に答える
1

使用している方法よりもそれほど複雑ではないふるい方法を使用してこれを行うこともできます。アイデアは、最初の n 個の連続する素数を選択し、それらを使用してふるいを構築することです。別の質問への回答で（証明とともに）議論し、Sheldon L. Cooper は彼の で実装を提供しています。彼がそうするために十分な賛成票を獲得したとは思わない（私はすでに「良い答え」を得ているので、それについて彼を助けることができるかもしれない.

したがって、ふるい数を計算した後は、ふるいと一致し、 の平方根より小さい数で割り切れるかどうかをテストするだけで済みますn。

于 2010-10-04T03:20:28.430 に答える
0

これは、実行に非常に長い時間がかかる場合があります。

これを追加して進行状況を確認します (ただし、さらに時間がかかります)。

for(i=2;i<num;i++)
    {
        if(num%i==0)
        {
            flag=0;
            printf("%d,", num); /* <== show the prime */
            break;
        }
    }

編集

他の人が指摘しているように、これは素数を数える最も遅い方法です。おそらく、あなたの課題の目的は、より速いものを調べて (そして実装して) もらうことでしょうか?

于 2010-10-04T02:42:40.863 に答える
0

あなたのプログラムは整数オーバーフローを引き起こします。それを修正するために long long を使用できます。

また、数値が素数かどうかをチェックするアルゴリズムはあまり良くありません。同様に簡単な別の方法は、数値 2 を数値の平方根にテストすることです。素数かどうかを判断するには、数の平方根までチェックする必要があります。

于 2010-10-04T02:58:11.493 に答える
0

簡単な変更で、プログラムの実行速度と実行する作業量が表示されます。約 100 回の反復ごとにステータスを出力するのは簡単です。(または、1000 回または 10000 回の反復に設定することもできます。)

でループの速度を2 倍にできることを認識してくださいIsPrime。
2 をチェックした後は、奇数をチェックするだけで済み、i+=2の代わりに で進めることができi++ます。

速度が気になるなら、なぜ偶数のチェックにそんなに時間をかけているのでしょうか? (奇数のみを開始したら、出力テストも奇数に変更する必要があることに注意してください)

偶数を避けることで、ループの速度を2倍にすることもできます。main(ここでも、2 を特殊なケースにし、i+=2 を使用して、3 から 3、5、7、9 を取得する必要があります....)

ループインIsPrimeを 2 倍の速度で実行し、ループインmainを 2 倍の速度で実行すると、プログラムは4 倍速くなります。(以前は 1 時間かかった場合、現在は 15 分になります。)

sqrt(num)あなたが行うことができる他の大きな速度の改善は、の代わりにへのループのみを実行することですnum

などの浮動小数点関数を持ち込むのは嫌いなのでsqrt、代わりに、sqrt 境界を通過してから 100 回の反復以内に停止し、定期的にステータスの更新を表示する近似値を提案します。

if (num%2 == 0)
{
    flag=0;
    return flag;
}

/* Now that we checked 2, we only need to check odd numbers from now on. */
for(i=3;i<num;i+=2)
{
    if (i%101 == 0)
    {
        printf("i is %d out of %d\n", i, num);
        if (i*i > num)
        {
            break;  /* If you pass the sqrt boundary, quit. */
        }
    }

    if(num%i==0)
    {
        flag=0;
        break;
    }
}

PSこのコードを C# プロジェクトに入れました (マイナーな移植)。確かに、これは現在、より優れたコンパイラと 2.8 GHz CPU を備えた 64 ビット OS で実行されていました。
20秒弱で走りました。

于 2010-10-04T03:02:30.893 に答える