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

Problem

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

입력

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

출력

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

---

Solve

1. 내 풀이 (에라토스테네스의 체)

#include <stdio.h>
#define mil 1000000

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

나는 에라토스테네스의 체를 m부터 n까지의 수에 대해서 적용하여 소수를 구하였다.

나누어지는 수의 init-expr를 i, iterator를 j += i로 설정하여 재간을 부려봤다.

2. 반복문

사후적 풀이   필자는 이 풀이를 생각하지 못했다.

만약 범위에 1이 있다면 1은 소수가 아니기에 iterate 한다.

i가 j에 의해 나누어 떨어지는 지 조사하기 위해 j를 $2$부터 $\sqrt{i}$까지¹ iterate 한다.

i가 j에 의해 나누어 떨어질 경우 i는 소수가 아니기에 조사를 중단하고 다음 i를 조사한다.

#include <stdio.h>
#include <math.h>

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

반복문을 사용할 수 있다는 점은 생각하였지만, 제곱근까지만 iterate 하여 시간복잡도를 줄이는 방법은 생각하지 못했다.

Python으로 위를 구현하면 다음과 같다.

m, n = map(int, input().split())
for i in range(m, n + 1):
    if i == 1: continue
    for j in range(2, int(i ** 0.5) + 1):
        if i % j == 0: break
    else: print(i)

Reference

Baekjoon

1. $\sqrt{i}$까지만 iterate 하는 이유는 $i$가 $j$에 의해 나누어 떨어지는 경우, $i$는 $j$의 배수이기에 $j$는 $\sqrt{i}$보다 작거나 같기 때문이다.
   가령 $16$이 약수인지 조사하기 위해 우리는 $4$까지만 조사하면 된다. ↩︎