埃及筛的理解

埃拉托斯特尼筛法 又称 埃及筛

核心思想为 某个质数*x（x为大于2的正整数）后 这个数必为合数

操作方法为：

如计算1~n区间内的质数个数

创建一个大小为n+1的数组judge 初始化全为0 0表示质数

首先从2开始遍历每一个数（1既不是质数也不是合数）遍历终点为

若该数i为质数 则从judge[i*2] 开始到 judge[i*i]  改变其值为1 1表示合数

当遍历到时 若其为质数 则已将n标记为合数 这便是遍历终点为的原因

至此遍历judge数组即可得到区间内质数的个数（注意从2开始遍历 1既不是质数也不是合数！）

上代码：

int countPrimes(int n) {int* judge = new int[n+1];for (int i = 0;i < n;i++){judge[i] = 0;}for (int i = 2;i <= sqrt(n);i++){if (iszs(i)){for (int j = i * 2;j <= n;j += i){judge[j] = 1;}}}int count = 0;for (int i = 2;i < n;i++){if (judge[i] == 0){count++;}}return count;
}