素数:缺少一些

Question

在标记为重复之前阅读:

我不想知道别人怎么做或者什么更快,我想通过自己来做.

问题:

我在计算的素数和实数(约1%)之间略有不同.我无法发现错误在哪里...

例如 :

从2到5万:

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;
}

Answer 1

我认为这:

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,这解释了正确结果(最高50000为5133)和你自己(5182)之间49的差异.