-1

重複としてフラグを立てる前に、これを読んでください：

他の人がどうするか、何が速いかなんて知りたくない、自分でやりたい。

問題：

計算された素数と実際の素数の間にはわずかな違いがあります (約 1%)。エラー箇所がわかりません...

例えば ​​：

2 から 50 000 まで:

Wolfram|Alphaは 5 132 を返し、私のアルゴリズムは 5 182 を返します

2 から 500 000 まで:

Wolfram|Alphaは 41 537 を返し、私のアルゴリズムは 41 665 を返します

私は間違っていて、Wolfram | Alphaは正しいと思いますので、ここに私のコードがあります:

#include <QCoreApplication>
#include <QVector>
#include <QDebug>

QVector<int> tabPrime;
bool isPrime(int n)
{
    bool boolIsPrime = true;
    int i = 0;

    while (boolIsPrime && tabPrime.at(i) * tabPrime.at(i) < n)
    {
        if (n % tabPrime.at(i) == 0)
            boolIsPrime = false;
        i++;
    }

    if(boolIsPrime)
        tabPrime.append(n);

    return boolIsPrime;
}


int main()
{
    int numberWanted = 500000;
    tabPrime.append(2);
    tabPrime.append(3);
    for(int i = 4; i < numberWanted; i++)
        isPrime(i);

    qDebug() << "There is" << tabPrime.count() << "primes numbers from 2 to" << numberWanted;
    return 0;
}
4

2 に答える 2

2

あなたの方法は、これまでに見つかった最大の素数の完全な正方形を追加することがあります。交換

boolIsPrime && tabPrime.at(i) * tabPrime.at(i) < n

と

boolIsPrime && tabPrime.at(i) * tabPrime.at(i) <= n

これはideoneのデモです。

于 2013-10-23T16:35:29.493 に答える