[BOJ/C++] 1929 소수 구하기

문제

https://www.acmicpc.net/problem/1929

풀이

에라토스테네스의 체 (소수 판별 알고리즘)

💡 대량의 소수 한꺼번에 판별해야 할 경우에 이용

1. 배열 생성해서 초기화
2. 2의 배수 지움, 3의 배수 지움, 4의 배수 지움 ⋯ (이미 지워진 경우는 건너 뜀)
3. 남아있는 수가 소수!

코드

#include <iostream>

using namespace std;

int arr[1000001];

int main() {
	int a, b;

	cin >> a >> b;

	for (int i = 2; i <= b; i++) {
		arr[i] = i;
	}

	for (int i = 2; i*i <= b; i++) {
		if (arr[i] == 0)	continue;
		for (int j = 2 * i; j <= b; j += i) {
			arr[j] = 0;
		}
	}

	for (int i = a; i <= b; i++) {
		if (arr[i] != 0)
			cout << i << '\n';
	}

	return 0;
}