baekjoon 1929

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

---

Idea

처음엔 이전에 하던 방식으로 뚞딱 하고 제출했는데

?ㅋㅋ 뭔가 문제가 있어보인다. 코드를 보면

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void) {
	int m, n, cnt = 0;	
	int dp[10001] = { 0, };

	scanf("%d %d", &m, &n);

	for (int i = m; i <= n; i++) {		
		int flag = 0;

		if (i == 1) {
			continue;
		}

		for (int j = 2; j < i; j++) {
			if (i % j == 0) {
				flag = 1;
			}
		}

		if (flag == 0) {
			dp[cnt++] = i;
		}
	}

	for (int i = 0; i < cnt; i++) {
		printf("%d\n", dp[i]);
	}

	return 0;
}

당연히 오류가 생길 만하다. 시간제한이 2초로 걸려있는 문제에서 시간복잡도를 줄이는 것은 굉장히 중요하다. 이런 수학 문제에서 시간복잡도를 줄이는 방법은 그 원리를 파악하고 최대한 간결하게 코드를 짜야한다.

우선 소수의 작동 원리를 검색해봤다.

보면 2에서 부터 배수들을 지워가는 모습이다. 위 그림을 보고 NL JOIN를 떠올렸다.
소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이기 때문에 약수가 존재할 수 없고 약수가 존재하지 않는다는 것은 1을 제외한 모든 수의 곱 조합으로 소수가 나올 수 없다.

배열을 모두 0으로 초기화하고 2 * 2 부터 n * n 까지 모두 1로 채워준 다음, 0이 들어있는 원소의 인덱스를 차례대로 출력하면 된다.

---

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void) {
	int m, n, arr[1000001] = { 0, };
	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;
}

후