给定范围之间有多少个素数？C[重复]

Question

所以，我做了这个小程序。它给出了所有正确的输出，但当它上传到网上法官扔我一个时间限制超过。有什么办法让它更有效率吗？

这是我的代码。

int const MAX = 1000001;  
#include<iostream> 
#include<string>
#include<cmath>

using namespace std;

int main()
{
    int count = 0, array[MAX], a, b, pi = 0;  
    bool end = false;

for(int i = 1; i <= MAX; i++)
{
    count = 0;
    for(int j = 2; j <= sqrt(i); j++)
    {
        if(i % j == 0)
        {
            array[i]=0;
            count++;
            break;
        }
    }
    if(count == 0 && i != 1){
        array[i]=1;
    }
}

do {
    cin >> a >> b;
    pi = 0;
    if ((a == 0) && (b == 0)) {
        end = true;
        break;
    }
    else {
        for (int i = a; i <= b; i++) {
            if (array[i] == 1) {
                pi ++;
            }
        }
        cout << pi << endl;
    }
} while (end == false);
cout << endl;

return 0;
}

Answer 1

您可以考虑使用埃拉托斯特尼的筛子。它是一种高效的素数生成算法。