[210401][백준/BOJ] 1929번 소수 구하기

문제

입출력

풀이

소수는 1과 자기 자신만으로 나누어지는 수를 의미한다. 이를 반대로 생각하면 어떤 수의 배수는 소수가 될 수 없다. 이를 활용한게 에라토스테네스의 체이다. 에라토스테네스의 체는 자기 자신을 제외한 자신의 배수들을 제거하면서 소수를 찾는 방법이다.
따라서 에라토스테네스의 체로 문제를 해결할 수 있다.

1. i가 2일때 2의 배수인 4 6 8 10 12... 을 제거한다.
2. i가 3일때 3의 배수인 6 9 12 15 18... 을 제거한다.
3. i가 4일때 4의 배수인 8 12 16 20... 을 제거한다.
4. 1 ~ 3을 반복하면 소수를 구할 수 있게 되며 시간 복잡도는 O(nlog logn) 이다.
   
   https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

코드

#include <bits/stdc++.h>
using namespace std;
#define SIZE 1000002

bool p_list[SIZE];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);	
	
	int m, n;
	cin >> m >> n;

	for (int i = 2; i <= n; ++i) // 0과 1은 0으로 나머지는 1로 초기화
		p_list[i] = 1;

	for (int i = 2; i <= n; ++i) // 2부터 입력값까지
	{
		if (p_list) // true 라면
		{
			// i가 2라면 4 6 8 10.. 0
			// i가 3이라면 6 9 12 15.. 0
			// i가 k라면 2*k 3*k 4*k.. 0
			// 이렇게 자기 자신의 2배 값부터 지워나감
			for (int j = 2 * i; j <= n; j += i) 
				p_list[j] = 0;
		}
	}
	
	for (int i = m; i <= n; ++i)
		if (p_list[i])
			cout << i << ' ';
}