[백준 C++] 1929 소수 구하기 - 에라토스테네스의체

1929번: 소수 구하기

#include <iostream>
using namespace std;

bool PrimeNumber[1000001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int M, N;
	cin >> M >> N;

	for (int i = 2; i <= N; ++i)
	{
		PrimeNumber[i] = true;
	}

	for (int i = 2; i <= N; ++i)
	{
		if (!PrimeNumber[i])
		{
			continue;
		}

		for (int j = 2; i * j <= N; ++j)
		{
			PrimeNumber[i * j] = false;
		}
	}

	for (int i = M; i <= N; ++i)
	{
		if (!PrimeNumber[i])
		{
			continue;
		}

		cout << i << '\n';
	}
}

---

 

에라토스테네스의 체 기법으로 주어진 구간의 모든 소수를 구하는 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. 구하고자 하는 소수의 범위만큼 1차원 배열 생성
2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. - 이때 처음으로 선택된 숫자는 지우지 않는다.
3. 배열의 끝까지 2를 반복한 후 배열에서 남아 있는 구간 내의 모든 수를 출력