[BOJ] 1929 - 소수 구하기

정수 M과 N을 입력받아 M 이상 N 이하의 소수를 오름차순으로 한 줄에 하나씩 출력하는 문제이다.

(1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

---

첫 번째 작성 코드

#include <stdio.h>

void getDecimal(int m, int n)
{
	int isdecimal;

	if (m == 1)
		m++;

	for (m; m < n; m++)
	{
		isdecimal = 0;

		for (int i = 2; i < m; i++)
		{
			if (m % i == 0)
				isdecimal = -1;
		}
		if (isdecimal == 0)
			printf("%d\n", m);
	}
}

int main(void)
{
	int m, n;
	scanf("%d %d", &m, &n);
	getDecimal(m, n);

	return 0;
}

위의 코드는 getDecimal 함수를 선언하여 함수 내에서 소수인 숫자를 출력한다.

m부터 1씩 증가하며 n이 될 때까지 for 문을 사용하여 반복한다.

m이 소수인지 확인하기 위한 변수 isdecimal를 0으로 초기화 한다.

내부에서 다시 for 문으로 i가 2부터 m이 될때까지 반복한다.

만약, m이 i로 나누어 떨어지면(소수가 아니면) isdecimal의 값을 -1로 바꾼다.

내부의 for 문을 빠져나온 뒤 isdecimal의 값이 0이라면 소수라는 의미이므로 printf 문으로 m을 출력한다.

해당 코드를 실행 해보면 출력은 잘 되는데 시간초과 발생한다.

입력 범위가 크기 때문에 순회하며 소수를 구할 시 시간초과가 발생한다고 한다.

---

해결방법 - 에라토스테네스의 체

→ 소수를 찾는 빠르고 쉬운 방법이다.

2부터 N까지 모든 정수를 나열하고, 2부터 시작하여 배수를 지워나가는 방법으로 소수를 구한다.

에라토스테네스의 체로 소수 구하는 방법

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.

2. 2는 소수이므로 자기 자신을 제외한 2의 배수를 모두 지운다.

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

4. 이를 반복하여 구간 내의 소수를 구한다.

참고! 구하고자 하는 수의 범위가 120일 경우, 11² > 120 이므로 11보다 작은 수의 배수들만 지워도 충분하다.

작성 코드

#include <stdio.h>
#include <stdlib.h>

void primeNumberSieve(int m, int n) {

    int* arr = (int*)malloc(sizeof(int) * (n + 1));

    if (m == 1)
        m++;

    // 1. 배열을 생성하여 초기화한다.
    for (int i = 2; i <= n; i++) {
        arr[i] = i;
    }

    // 2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.
    // (지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
    for (int i = 2; i <= n; i++) {
        if (arr[i] == 0) continue; // 이미 지워진 수라면 건너뛰기

        // 이미 지워진 숫자가 아니라면, 그 배수부터 출발하여, 가능한 모든 숫자 지우기
        for (int j = 2 * i; j <= n; j += i) {
            arr[j] = 0;
        }
    }

    // 3. 2부터 시작하여 남아있는 수를 모두 출력한다.
    for (int i = m; i <= n; i++) {
        if (arr[i] != 0) printf("%d\n", arr[i]);
    }

    free(arr);
}

int main(void) {
    int m, n;
    scanf("%d %d", &m, &n);

    primeNumberSieve(m, n);
    return 0;
}