[C++] 백준 1929번: 소수 구하기

1929번: 소수 구하기

이번 문제는 입력이 최대 1,000,000까지다.

연산량이 적지 않은 만큼 입력에서도 신경을 써야 한다.

iostream을 이용할 경우 다음을 main 함수 아래에 추가하면 출력이 빨라진다.

ios_base::sync_with_stdio(false)

하지만 나는 printf/scanf를 사용하는 것을 선호한다.

이 문제를 풀고자할 때 제일 먼저 떠올리는 해결 방법이 아래 1번 방법이다.

 

1. M부터 N까지의 각 수에 대해 검사

#include <cstdio>
int main() {
	int M, N;
	scanf("%d %d", &M, &N);
	for (int i = M; i <= N; i++) {
		bool isPrime = true;
		if (i == 1)
			continue;
		for (int j = 2; j < i; j++) {
			if (i % j == 0) {
				isPrime = false;
				break;
			}
		}
		if (isPrime)
			printf("%d\n", i);
	}
	return 0;
}

M부터 N까지의 수에 대해 각각 1부터 나눠가며 소수임을 확인한다.

이 방법이 제일 흔하게 생각할 수 있으나, 예상했다시피 시간초과가 뜬다.

그래서 이를 좀 더 최적화 하고자 하면 2번 방법으로 할 수 있다.

 

2. M부터 N까지의 각 수에 대해 검사 - 연산 줄이기

#include <cstdio>
int main() {
	int M, N;
	scanf("%d %d", &M, &N);
	for (int i = M; i <= N; i++) {
		bool isPrime = true;
		if (i == 1)
			continue;
		for (int j = 2; j < i / 2; j++) {
			if (i % j == 0) {
				isPrime = false;
				break;
			}
		}
		if (isPrime)
			printf("%d\n", i);
	}
	return 0;
}

이 방법은 기존 j를 2부터 i - 1까지 검증하던 것을 i / 2까지만 검증하도록 했는데,

i의 최대 약수는 i / 2보다 크지 않기 때문이다.

하지만 이 방법 역시 시간초과가 뜬다.

힌트를 얻고자 페이지 하단의 알고리즘 분류 항목을 확인하면, "에라토스테네스의 체"라는게 뜬다.

 

3. 에라토스테네스의 체

#include <cstdio>

int main() {
	int M, N;
	scanf("%d %d", &M, &N);
	bool* pArr = new bool[N + 1];
	for (int i = 1; i <= N; i++)
		pArr[i] = true;
	pArr[1] = false;
	for (int i = 2; i <= N; i++) {
		if (pArr[i] == false)
			continue;
		for (int j = i + i; j <= N; j += i)
			pArr[j] = false;
	}
	for (int i = M; i <= N; i++)
		if (pArr[i])
			printf("%d\n", i);
	delete[] pArr;
	return 0;
}

이 경우 M, N을 입력받은 후, 크기가 N + 1인 bool 배열 pArr을 만든다.

계산상 편의를 위해 index와 대응하는 수를 일치시키므로 0번 인덱스는 이용하지 않는다.

pArr을 초기화할 때는 모두 소수라는 가정으로 true로 설정한다. (단, pArr[1]은 false로 한다.)

그 다음, 2부터 시작하여 에라토스테네스의 체의 정의대로 작업을 진행한다.

언뜻보면 작업량이 줄어든 것 같지 않으나, 값이 false인 경우는 스킵하므로 작업량이 많이 줄어듦을 알 수 있다.

작업이 끝나면 M부터 N까지 각 수에 대응하는 pArr의 값이 true일 때만 출력하면 끝이다.