1701非素数个数（考试前要复习筛查法）
#include<iostream>
using namespace std;
bool a[10000001] = { true };
void Prime(long long end) {
for (long long i = 2; i <= end; i++) {
a[i] = true;
}
for (long long i = 1; i * i <= end; i++) {
if (a[i]) {//素数的倍数全部不是素数置false
for (long long j = i * i; j <= end; j += i) {
a[j] = false;
}
}
}
}
int main() {
long long start, end;
while (cin >> start >> end) {
long long sum = 0;
Prime(end);
for (long long i = start;i <= end;i++) {
if (!a[i]) {
sum++;
}
}
if (start == 1) {
cout << sum - 1 << endl;
}
else {
cout << sum << endl;
}
}
return 0;
}
朴素筛查（埃氏筛查法）：
首先把2-n的数按顺序写出（例子为n=16）：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
从前往后看，找到第一个未被划掉的数，（这里是2）说...
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
写的很详细，赞一个