-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

6

我认为这:

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

应该:

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

您将素数平方视为素数。

50000 的平方根是 223.6... 从 2 到 223 有 48 个素数。您还附加了 3 两次(循环应该从 4 开始,而不是 3)。48+1 = 49,这解释了正确结果(5133 最多 50000)和你的(5182)之间的差异 49。

于 2013-10-23T16:40:27.143 回答
2

您的方法有时会添加迄今为止发现的最大素数的完整平方。代替

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

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

这是关于 ideone 的演示

于 2013-10-23T16:35:29.493 回答