[백준 알고리즘] 1929번 : 소수구하기 (C) 문제 풀이

문제

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

입력

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

출력

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

출처

• 데이터를 추가한 사람: jinjean0123, yongjun042

 

문제 풀이

이 문제에 경우에는 처음에는 구글링을 이용해서 풀었던 기억이 있다.

 

어렵게 생각할 건 없고, 에라토스테네스의 체를 이용하면 아~~~주 간단하게 문제가 해결이 가능하다.

 

이 문제에 경우 파이썬으로 풀었다가 자꾸 런타임 에러 (IndexError)가 떠서 그냥 C언어로 간단하게 해결했다.

#include <stdio.h>
 
 
 
int main() {
 
 
 
    int M, N, i, j;
 
    int arr[1000001] = { 1,1 };
 
 
 
    // 에라토스테네스의 체, 소수가 아닌수 = 1
 
    for (i = 2; (i * i) < 1000001; i++) {
 
        if (arr[i] == 0) {
 
            for (j = i * i; j < 1000001; j += i)
 
                arr[j] = 1;
 
        }
 
    }
 
 
 
    scanf("%d %d", &M, &N);
 
 
 
    // 범위 안의 소수를 구한다.
 
    for (i = M; i <= N; i++) {
 
        if (arr[i] == 0)
 
            printf("%d\n", i);
 
    }
 
 
 
    return 0;
 
 
 
}