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

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

1929번: 소수 구하기

 

 

처음에는 그냥 무작정 짝수 거르고 루프 돌렸더니 시간초과 뜸

 

그래서 찾아봤더니 '에라토스테네스의 체'라는 것이 있다카더라

 

에라토스테네스의 체는 특정 범위가 주어졌을 때 그 범위 내의 소수들을 판별할 수 있는 방법이다. 

마치 체로 거르듯 소수들의 배수를 지워나가다보면 남는 것은 소수임을 이용한다. 

 

 

2부터 수들을 나열한 다음, 2는 소수이므로 남겨두고 2의 배수들을 지운다. 

3 역시 소수이므로 남겨두고 3의 배수를 지운다. 

이런 방법으로 5, 7, 11...까지 반복한다. 

 

만약 범위가 2~120이라면 11의 배수까지 지워나가면 남은 수는 모두 소수가 된다. (120<11^2)

 

 

 

실제로 구현하기 위해선 bool형 배열을 만들고 2의 배수부터 지워나간 뒤 지워지지 않은 수중 가장 작은 수가 그 다음 소수인 것으로 간주해 그 수의 배수를 지워나가는 식으로 하면 된다. 

 

또한 N이라는 수의 소수 여부를 판별할 때, N-1까지 나눠보는 것이 아니라 N의 제곱근까지만 나눠봐도 판별할 수 있다는 사실 역시 적용하면 시간을 더 줄일 수 있다.

 

 

#include <iostream>

int main()
{
	int m, n;
	std::cin >> m >> n;

	bool arr[1000001] = { false, }; //false면 소수로 간주
	arr[0] = arr[1] = true;

	for (int i = 2; i * i <= n; ++i) //n의 제곱근의 배수까지만 지우면 된다.
	{
		if (arr[i]) continue; //i가 이미 지워진 수인 경우 continue
		else
		{
			for (int j = 2; j * i <= n; ++j) //i의 배수 지우기
			{
				arr[i * j] = true;
			}
		}
	}
    
	for (int i = m; i <= n; ++i) //false인 것만 출력
	{
		if (!arr[i]) std::cout << i << '\n';
	}
}

 

 

 

거르는 부분에서 범위가 m부터 시작이어도 2부터 걸러야 한다는 점은 조금...찝찝했는데 체를 쓰려면 이 방법밖에 없을 것 같아서 일단 이렇게 했다. 

그런데 m과 n의 가능한 범위가 이것보다 더 커지면 조금 비효율적일 것 같긴 하다.

 

또 처음엔 입력받은 m, n 범위에 맞춰서 동적배열을 만들까 했는데 시간이 더 오래걸릴 것 같아서 관뒀다. 

그리고 동적배열로 만들면 오히려 더 메모리를 쓰는 경우도 있더라

 

아, 그리고 내가 예전에 C++ 카테고리에 관련 글을 쓴 적이 있던 것 같은데, endl 조정자는 개행문자를 삽입할 뿐만 아니라 flush 함수(출력 버퍼 비우기)도 호출하므로 그냥 개행문자보다 시간이 더 오래걸린다. 

 

 

 

 

근데 이 문제만 20번 넘게 시도하다가 현타맞음(우리학교 랭킹 낮추는데 기여하고 옴....)

분명 잘 나오는 것 같은데 계속 출력 초과가 뜨는 바람에 삽질하느라 고생했다.

맞추고 나서 이 문제 티어 브론즈면 조금 빡칠 것 같았는데 다행히 실버였음.

 

 

참고로 어제 풀었는데 풀이를 개똥같이 해서 좀 손보느라고 오늘 올리는 거다.

1일 1백준 작심일일 하진 않았다고 변명하는거임...