[BOJ] 백준 1929번: 소수 구하기, 에라토스테네스의 체

 

어떤 수 X가 소수인지 판별하는 것은 O(lgX) 복잡도로 판별 가능합니다. 2~x^1/2 범위 내에서 하나라도 나누어 떨어지는 수가 있다면 그 수는 소수가 아니게 되죠.

범위 a~b 사이의 모든 수를 위의 아이디어로 판별한다고 해도 무리는 없습니다.

다만 우리는 좀 더 효율적으로 소수를 찾고 이를 활용할 수 있습니다.

특정 범위에 존재하는 수들 중 소수를 찾는 문제는 에라토스네테스의 체를 이용합니다.

www.acmicpc.net/problem/1929

1929번: 소수 구하기

1929번: 소수 구하기 문제는 N이 100만까지로 어떤 수 X가 소수인지 아닌지를 의미하는 bool 형 배열을 선언할 수 있습니다. 선언된 배열에서 체크된 수들은 소수가 아니라고 정합니다.

만약 N이 40이라면 위와 같은 배열을 선언하고 1은 소수가 아니므로 미리 체크해줍니다.

우리는 2부터 40까지 반복하면서 체크되지 않는 수의 배수들을 체크해나갑니다.

2는 체크가 되어있지 않으므로 2의 배수들을 지워 나간다면 아래와 같이 배열이 체크됩니다.

2의 배수들을 전부 지웠으므로, 다음 수 3의 배수들을 지웁니다.

그 다음 수 4의 배수들을 지우려고 보니, 이미 4는 소수가 아니라고 체크되어있습니다. 이는 4의 배수들은 모두 소수가 아니라고 이전에 체크됐음을 의미합니다.

이를 40까지 반복하면 아래와 같이 에라토스테네스의 체가 색칠됩니다.

1~40 범위 내의 소수는 2, 3, 5, 7 ,11, 13 ,17 ,19, 23, 29, 31, 37 이 존재함을 체를 통해 알 수 있습니다.

#include <iostream>
#include <math.h>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;

bool s[1000001] = { 0, };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	s[1] = 1;
	for (int i = 2; i <= 1000000; i++) {
		if (!s[i]) {
			for (int j = i + i; j <= 1000000; j += i) {
				s[j] = 1;
			}
		}
	}
	int ans = 0;
	int st, ed, _min=-1; 
	cin >> st >> ed;
	for (int i = st; i <= ed; i++) {
		if (!s[i]) {
			cout << i << "\n";
		}
	}
}