1022: [编程入门]筛选N以内的素数

解题思路:

简单素数筛选法的原理：一个数不管是不是素数，它的倍数都一定不是素数。所以我先定义一个bool数组，素数都是0，用简单素数筛选法把非素数改成1。

注意事项:

（1）本来想写成for循环嵌套，最外面是for (int i = 2; i < max && !res[i]; i++)，但结果不对，原因是当 i 走到第一个非素数（“4”）时就不会往下走了。所以还是得用while()把条件分开。

（2）现代码待优化的地方：i = 2 的时候会计算一次 res[50] = 1，i = 5 的时候还会再计算一次 res[50] = 1，诸如此类的重复运算会出现多次。

参考代码:

#include <iostream>

using namespace std;

void primeSelect(int max); //输出max以内的素数
int main() {
	int N = 0;
	cin >> N;
	primeSelect(N);
	return 0;
}
void primeSelect(int max) {
	bool res[max] = {0}; //0代表素数，初始化全0，找到非素数就改成1
	int i = 2;
	while(i < max) {
		if(!res[i]) { //如果这个数是1，说明已经被其因数筛过了，则其倍数也一定被其因数筛过了，直接pass
			for(int j = i; j <= max / i; j++) {
				res[i * j] = 1; //简单素数筛选法的原理：两数之积一定不是素数
			}
			cout << i << endl;
		}
		i++;
	}
}