0

このプログラムは、エラトステネスのふるいを使用して素数を計算するc++プログラムです。次に、これを行うのにかかる時間を保存し、計算を100回再実行して、毎回時間を保存することになっています。このプログラムで私が助けを必要としていることが2つあります。

第一に、私はそれより高くなりたい4億8000万までの数しかテストできません。

第二に、私がプログラムの時間を計るとき、それは最初のタイミングだけを取得し、次に時間としてゼロを出力します。これは正しくなく、時計の問題が何であるかわかりません。-助けてくれてありがとう

これが私のコードです。

#include <iostream>
#include <ctime>
using namespace std;

int main ()
{


    int long MAX_NUM = 1000000;
    int long MAX_NUM_ARRAY = MAX_NUM+1;
    int long sieve_prime = 2;
    int time_store = 0;
    while (time_store<=100)
    {
        int long sieve_prime_constant = 0;

        int *Num_Array = new int[MAX_NUM_ARRAY];
        std::fill_n(Num_Array, MAX_NUM_ARRAY, 3);
        Num_Array [0] = 1;
        Num_Array [1] = 1;


        clock_t time1,time2;
        time1 = clock();
        while (sieve_prime_constant <= MAX_NUM_ARRAY)
        {
            if (Num_Array [sieve_prime_constant] == 1)  
            {

                sieve_prime_constant++;
            }
            else
            {
                Num_Array [sieve_prime_constant] = 0;  
                sieve_prime=sieve_prime_constant; 
                while (sieve_prime<=MAX_NUM_ARRAY - sieve_prime_constant)  
                {
                    sieve_prime = sieve_prime + sieve_prime_constant;
                    Num_Array [sieve_prime] = 1;
                }
                if (sieve_prime_constant <= MAX_NUM_ARRAY)
                {
                    sieve_prime_constant++;
                    sieve_prime = sieve_prime_constant;
                }
            }
        }
        time2 = clock();
        delete[] Num_Array;
        cout << "It took " << (float(time2 - time1)/(CLOCKS_PER_SEC)) << " seconds to    execute    this loop." << endl;
        cout << "This loop has already been executed " << time_store << " times." << endl;
        float Time_Array[100];
        Time_Array[time_store] = (float(time2 - time1)/(CLOCKS_PER_SEC));
        time_store++;
    }


    return 0;

}
4

3 に答える 3

0

コードのこのセクションは、ループ内に入るはずです。

int *Num_Array = new int[MAX_NUM_ARRAY];
std::fill_n(Num_Array, MAX_NUM_ARRAY, 3);
Num_Array [0] = 1;
Num_Array [1] = 1;

編集：そしてこれもループにある必要があります：

int long sieve_prime_constant = 0;

これを自分のマシンで実行すると、ループごとに0.2秒かかります。MAX_NUM_ARRAYに2つのゼロを追加すると、反復ごとに4.6秒かかります（20番目のループまで、1.5分以上待つのに飽きました）

于 2013-02-10T22:27:59.733 に答える
0

問題は、開始プライムをリセットしないことだと思います。

int long sieve_prime = 2;

現在、それはあなたのループの外にあります。考え直して...それは問題ではありません。このコードは、Mats Peterssonの回答に提案を組み込むように編集されていますか？悪いインデントを修正しました。

とにかく、あなたの質問の他の部分については、のchar代わりに使用することをお勧めintしますNum_Array。intブール値を格納するために使用する必要はありません。を使用charすることで、同じ量のメモリに約4倍の値を格納できるはずです（int32ビットであると仮定すると、おそらくそうです）。

つまり、最大20億までの数を処理できるということです。signed longの代わりにタイプとして使用しているのでunsigned long、とにかく計算の数値制限に近づいています。

さらに少ないメモリを使用したい場合は、を使用できますがstd::bitset、パフォーマンスが大幅に低下する可能性があることに注意してください。

ちなみに、タイミング配列は次の先頭で宣言する必要がありますmain。

float Time_Array[100];

使用する直前にループ内に配置するのは少し面倒です。

ああ、そしてあなたが興味を持っている場合に備えて、これが私自身のふるいの実装です。個人的には、あなたよりも読みやすいと思います。

std::vector<char> isPrime( N, 1 );

for( int i = 2; i < N; i++ )
{
    if( !isPrime[i] ) continue;
    for( int x = i*2; x < N; x+=i ) isPrime[x] = 0;
}
于 2013-02-10T23:07:20.487 に答える
0

以前のコメントに同意します。本当に物事をやりたい場合は、すべての可能な値の配列（intまたはcharなど）を格納するのではなく、素数のみを保持します。次に、これまでに見つかったすべての素数の除算性について、後続の各数値をテストします。現在、保存できる素数の数によってのみ制限されます。もちろん、これは実際にはもう実装したいアルゴリズムではありません...しかし、整数除算を使用するため、非常に高速です。このようなもの：

int myPrimes[MAX_PRIME];
int pCount, ii, jj;
ii = 3;
myPrimes[0]=2;
for(pCount=1; pCount<MAX_PRIME; pCount++) {
    for(jj = 1; jj<pCount; jj++) {
        if (ii%myPrimes[jj]==0) {
            // not a prime
            ii+=2; // never test even numbers...
            jj = 1; // start loop again
        }
    }
    myPrimes[pCount]=ii;
}

本当にあなたが求めていたものではありませんが、多分それは役に立つでしょう。

于 2013-02-10T23:30:18.300 に答える