1084: 用筛法求之N内的素数。

解题思路:

（1）记得之前做过一样的题目发过题解了，这次的区别可能就是用 vector 构造数组了吧。

（2）原理很简单，不管一个数是不是素数，它自身的倍数一定不是素数，建一个 bool 数组不停地遍历+标记就行了。

（3）运算次数肯定比传统的找素数要少，但空间应该更多了，毕竟多建了一个数组。所以说这属于空间换时间吗？

注意事项:

不用管数组的第 i 个元素对应 i + 1 这种事，因为这只是个用于标记的 bool 数组，把下标当成实际数字就行了。

参考代码:

// 题目 1084: 用筛法求之N内的素数。
#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n = 0;
	cin >> n;
	vector<bool> isPrime(n, 1); // 构造一个大小为 n 的全 1 数组
	for (int i = 2; i < n / 2; ++i) {
		if (isPrime[i]) {
			for (int j = i * 2; j < n; j += i) {
				isPrime[j] = 0; // 一个数的倍数一定不是素数
			}
		}
	}
	for (int i = 2; i < n; ++i) {
		if (isPrime[i]) {
			cout << i << endl;
		}
	}
	return 0;
}