1

私は自分で Sieve を実装しようとしていますが、提供されたアルゴリズム以外の助けはありません...

#include <iostream>

using namespace std;

void findPrimeNumbers(int number) {

    int n=0;

    bool* boolArray = new bool[number](); 

    for(int i=0; i<number; i++) {
        boolArray[i] = true;
    }

    for(int i = 2; i<(int)sqrt(number); i++) {
        cout << "calculating...\n";
        if(boolArray[i]) {
            for(int j=(i^2+(n*i)); j<number; n++)
                boolArray[j] = false; 
        }
        if(boolArray[i])
            cout << i << "\n";
    }
    return;
}

int main()
{

    findPrimeNumbers(55);

    system("pause");
    return 0;
}

ただし、プログラムは 37 行目でハングしています。具体的には、「boolArray[j] = false」です。そのループから抜け出せず、その理由がわかりません。

編集済み：わかりました、これでハングは修正されますが、まだ正しくありませんが、答えないでください。理解したいです:)

#include <iostream>
#include <cmath>

using namespace std;

void findPrimeNumbers(int number) {

    int n=0;

    bool* boolArray = new bool[number](); 

    for(int i=0; i<number; i++) {
        boolArray[i] = true;
    }

    for(int i = 2; i<sqrt(number); i++) {
        if(boolArray[i]) {
            for (int j = pow(i,2) + n*i; j <= number; j = pow(i, 2) + (++n*i))
                boolArray[j] = false;
        }
        if(boolArray[i] && number % i == 0)
            cout << i << "\n";
    }
    return;
}

int main()
{

    findPrimeNumbers(13195);

    system("pause");
    return 0;
}
4

4 に答える 4

0

あなたの問題はi^2+(n*i)、コメントが指摘するような行operator^であり、指数ではなくXOR演算子です。何かを累乗するには、<cmath>ヘッダーを含めstd::pow(a,b)て、数式と同等の場所で呼び出す必要がありますa^b。

コード レビューは求めていませんが、bool 配列に動的割り当てを使用することはおそらく良い考えではないことに注意してください。std::vector<bool>と適切なreserve呼び出しを使用する必要があります。また、呼び出しはそれ自体で乗算するだけなので、完全に不要であることに注意してpowください (つまり、2^2 は 2*2 と同じです)。

より良いナイーブ プライム シーブは、次のようなものになります。

#include <vector>
#include <iostream>

template<typename T>
std::vector<T> generatePrimes(unsigned int limit) {
    std::vector<T> primes;
    std::vector<bool> sieve((limit+1)/2);
    if(limit > 1) {
        primes.push_back(2);
        for(unsigned int i = 1, prime = 3; i < sieve.size(); ++i, prime += 2) {
            if(!sieve[i]) {
                primes.push_back(prime);
                for(unsigned int j = (prime*prime)/2; j < sieve.size(); j += prime)
                    sieve[j] = true;
            }
        }
    }
    return primes;
}

int main() {
    std::vector<unsigned> primes = generatePrimes<unsigned>(1000000);
    for(auto& i : primes)
        std::cout << i << '\n';
}

ここで見ることができます。

于 2013-01-26T03:41:31.620 に答える
0

@Rapptz (^ はビットごとの xor) によって指摘されたエラーを超えて、j ではなく n をインクリメントしているため、終了条件に到達することはありません。

于 2013-01-26T03:42:03.833 に答える
0

いくつかの問題があります。

int j=(i^2+(n*i))

^は C++ では強力ではなく、ビット単位の XOR 演算子です。これを修正するには、 を使用するか、単に を使用する必要が#include <cmath>あります。powi * i

第二に、他の人が述べたように、あなたは増加していますn。これを最も簡単に修正するには、while代わりにループを使用します。

int j = std::pow(i, 2) + (n*i);
while(j < number) {
    //Set bool at index to false
    j += i;
}

new第三に、メモリ リークがありますdelete。さらに、ここで使用する理由はありませnewん。代わりに、次のようにする必要があります。

bool b[number];

これにより、関数の終了時に b の割り当てが自動的に解除されます。

最後に、なぜ関数returnの一番下にあるのでしょうか? void技術的にはできますが、そうする理由はありません。

于 2013-01-26T03:43:14.433 に答える
0

2 つの問題:

^演算子は、他の言語のような指数演算子ではありません。i代わりにそれ自体で乗算するだけです（ i*i）。

あなたのforループ:

for(int j=(i^2+(n*i)); j<number; n++)
    boolArray[j] = false;

ループごとに初期条件を再評価しません。forループの開始時に条件を再評価する必要があります。

for(int n=0; j<number; n++)
{
    j=(i*i+(n*i));
    boolArray[j] = false; 
}
于 2013-01-26T03:46:05.750 に答える