백준 1929번

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

---

생각나는대로 코드를 짠 후 넣었더니 시간 초과가 떴다. 기본적으로 이 문제를 보고 떠올리는 방식으로 제출을 하면, 십중팔구 시간 초과가 뜬다고 한다.

#include <stdio.h>

int main(void) {
	int m, n;
	scanf("%d %d", &m, &n);
	int count = 0;
	for (int i = m; i <= n; i++) {
		if (i == 1) {
			continue;
		}
		else if (i == 2) {
			printf("2\n");
			continue;
		}
		else {
			for (int j = 2; j < i; j++) {
				if (i % j == 0) {
					count++;
					break;
				}
			}
			if (count == 0) {
				printf("%d\n", i);
			}
			count = 0;
		}
	}
	return 0;
}

원래 제출했던 코드는 이렇다. 하지만, 에라토스테네스의 체라는 것을 조금 더 생각해볼 필요가 있었다.

에라토스테네스의 체란, 고대 그리스 수학자인 에라토스테네스가 발견한 소수를 찾는 방법 중 하나이다.
참고 자료(위키백과)

먼저, 자신이 구하고자 하는 범위의 수들을 쭉 나열한다. 그 후, 2부터 시작하여 자기 자신을 제외한 2의 배수를 모두 지운다.

남아있는 수들 중 3 또한 소수이므로 자기 자신을 제외한 3의 배수를 모두 지운다.

또한 남아있는 수들 중 5도 소수이므로 자기 자신을 제외한 5의 배수를 모두 지운다.

위 과정을 반복한다면, 남는 것은 소수밖에 없을 것이다.

이러한 과정을 프로그래밍 언어로 구현하면 밑의 코드와 같아질 것이다:

#include <stdio.h>

int arr[1000000];

int main(void) {
	int m, n;
	arr[1] = 1;
	scanf("%d %d", &m, &n);
	for (int i = 2; i <= n; i++) {
		for (int j = 2; i * j <= n; j++) {
			arr[i * j] = 1;
		}
	}
	for (int i = m; i <= n; i++) {
		if (arr[i] == 0) {
			printf("%d\n", i);
		}
	}
	return 0;
}