[02. 기본 자료구조] N 이하의 소수 구하기

Point1 2를 제외한 소수는 홀수이므로 홀수만 점검 (n : 홀수)
Point2 square root 까지만 점검.
Point3 에라토스테네스의 체의 원리

#include <iostream>
#include <vector>
using namespace std;

int main() {
	const int N = 1000;
	vector<int> primes = { 2, 3 };
	primes.reserve(N/2);
	for (int n = 5; n <= N; n += 2) {							// point 1
		bool flag = false;

		for (int i = 1; primes[i] * primes[i] <= n; i++) {		// point 1, 2
			if (n % primes[i] == 0) {							// point 3
				flag = true;
				break;
			}
		}
		if (!flag)
			primes.push_back(n);
	}
	for (int prime : primes)
		cout << prime << endl;
}