Allen 问题 A 【基础】素数问题内存限制：64 MB 时间限制：1000 S评测方式：文本比较 命题人：外部导入提交：66 解决：32题目描述编一个程序计算1-n范围内素数的个数。输入包括多组数据。每组数据仅有一个整数n 1=n=10000000。输入以0结束。输出对于每组数据输入输出一行为1-n包括n之间的素数的个数。样例输入 复制110651000样例输出 复制041825来源分类数组问

#include #include

using namespace std;

int countPrimes(int n) { vector isPrime(n+1, true); isPrime[0] = false; isPrime[1] = false;

for (int i=2; i*i<=n; i++) {
    if (isPrime[i]) {
        for (int j=i*i; j<=n; j+=i) {
            isPrime[j] = false;
        }
    }
}

int count = 0;
for (int i=2; i<=n; i++) {
    if (isPrime[i]) {
        count++;
    }
}

return count;

}

int main() { int n; cin >> n;

while (n != 0) {
    cout << countPrimes(n) << endl;
    cin >> n;
}

return 0;