[Baekjoon] 1929_소수 구하기

* 최대 시행 횟수가 1,000,000개가 넘어가는 프로그램에 시간복잡도가 n^2인 로직을 넣으면

 BOJ에서는 바로 시간초과를 낸다. 따라서 더 효율적인 로직으로 소수를 구해야 하는데, 이때

사용될 수학 원리가 바로 '에라토스테네스의 체'이다.

 

* 에라토스테네스의 체란, 어떤 수 n보다 작은 소수들을 모두 구할 때, 2 <= m < n인 수에 대해

 m=2부터 시작하여, n보다 작은 모든 수들을 나눴을 때 자기 자신이 아닌 수로 나눠지면 지우고, 다음 수 m=3으로 나눴을 때도 자기 자신이 아닌 수로 나눠지면 지우는 방식으로 m=n-1까지 돌렸을 때 남는 수가 소수라고 생각할 수 있다.

 

** 설명이 이상하지만, 원리는 같다.

 

* C++로 구현했는데, 에라토스테네스의 체를 이용한 내 생각대로 구현해봐도 시간초과가 나서 새로운 개념을 배웠다.

 바로 std::ios_base::sync_with_stdio(false)와 std::cout.tie(NULL) 코드이다.

std::ios_base::sync_with_stdio(false)를 이용하면 c의 stdio의 버퍼와 연결해제되어 iostream에서 c의 버퍼는 더이상 이용할 수 없게 되지만 수행속도는 빨라진다는 장점이 있다.

std::cout.tie(NULL)는 기존에 한 쌍으로 묶여있던 cin과 cout버퍼를 분리해주는 것이다. 수없이 많은 횟수의 입출력을 반복해야 하는 알고리즘문제의 특성상 필수적으로 버퍼를 분리해주는 것이 좋다.

 

 

** 시간초과 해결에 대한 아이디어를 구하던 중 신박한 해결책을 알게 되었다.

 바로 소수를 구하는 로직에서, 소수를 판정할 때 나눠주는 수의 범위를 전체의 sqrt를 해줘도 상관없다는 것이다.

 

왜 그럴까?

 

전체 범위를 sqrt한 값이 해당로직의 가운데 경계가 되기 때문이다.

N = 16인 경우를 생각해보면, sqrt(N) = 4를 중심으로 이전과 이후의 실행은 똑같은 알고리즘이 된다.

따라서 i <= sqrt(16) = 4 인 경우만 실행해 줘도 된다는 의미이다.

제곱근을 이용하여 범위를 지정해 줄때는 부등식에 등호조건이 무조건 들어가야 한다. 그래야 전체 범위를

포괄해주기 때문이다. 등호조건이 없다면 경계가 되는 부분이 반복문에 포함되지 않는다는 말과 같다.

 

 

#include <iostream>

using namespace std;

// 소수 구하기
// 더 적은 시간의 알고리즘
int main() {
	ios_base::sync_with_stdio(false); cout.tie(NULL);
	int M, N; cin >> M >> N;
	int* a = new int[N]();

	for (int i = 1; i <= N; i++) {
		a[i - 1] = i;
	}
	a[0] = 0;
	// i의 범위 설정할 때 sqrt를 썼으면 등호를 무조건 붙여줘야 함
	for (int i = 2; i*i <= N; i++) {
		for (int j = M-1; j < N; j++) {
			if (a[j] == 0) {
				continue;
			}
			if (a[j] % i == 0 && a[j] != i) {
				a[j] = 0;
			}
		}
	}

	for (int i = M-1; i < N; i++) {
		if (a[i] != 0) { cout << a[i] << '\n'; }
	}
	delete[] a;
	return 0;
}