백준(BAEKJOON): 소수 구하기(1929번)

Source

문제

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

입력

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

출력

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

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

해설

입출력만 달리해서 같의 같은 문제가 연달아 있다. 이걸 또 풀어야 하나 싶었다. 그런데 이번 채점 결과를 보니 시간이 212ms였다. 이제까지 푼 문제 중에서 가장 많은 시간이 걸린 문제인 듯하다. 소수 여부를 판별하는 더 빠른 함수를 생각해 봐야겠다. 하지만 오늘은 귀찮으니 이전 문제에서 사용했던 CheckPrime() 함수를 재활용했다.

소스코드: C

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

int CheckPrime(int n);
int main(int argc, char *argv[])
{
    int m, n;
    scanf("%d %d", &m, &n);

    for (; m <= n; ++m) {
        if (CheckPrime(m)) printf("%d\n", m);
    }
    return 0;
}

int CheckPrime(int n)
{
    int i = 2;
    if (n == 1) return 0;

    while (1) {
        if ( i <= sqrt(n) ) {
            if ( n % i == 0 ) return 0;
            else i++;
        } else {
            return 1;
        }
    }
}