[C] 백준_1929번

1929번 소수 구하기 (silver 3)

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

 

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다.

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

 

출력

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

 

예제 입력 1

3 16

 

 

 

예제 출력 1

3
5
7
11
13

 

 

#include <stdio.h>

int main() { // 에라토스테네스의 체 사용
    int start, end;
    int arr[1000000] = {0};
    
    scanf("%d %d", &start, &end);
    for (int i = 0; i < 1000001; i++){
        arr[i] = 1;   // 배열의 인덱스의 원소를 다 1로 채움
    }
    for (int i = 2; i <= end; i++){
        for (int j = i * 2; j <= end; j += i){
            arr[j] = 0;   // 소수에 해당하지 않는 인덱스의 원소들은 다 0으로 채움
        }
    }
    for (int i = start; i <= end; i++){
        if (arr[i] == 1)
            printf("%d\n", i); // 배열의 원소가 1인 인덱스는 곧 소수에 해당 - 출력
    }
    return 0;

}

 

 

배열 없이 해보려다가 시간 초과가 돼서 구글링을 해보았더니 에라토스테네스의 체를 사용해서 풀어야 함을 알게되었다.

• 우선 m이상 n이하에서 m에 해당하는 수를 start, n에 해당하는 수를 end로 선언해주었다.
• start와 end는 1이상 1000000이기 때문에 크기가 1000000인 배열 arr을 선언해주고 0으로 초기화를 해주었다.
• 그 다음 2번 인덱스부터(소수는 2이상이기 때문) 배열의 끝인 1000000인덱스까지 배열의 원소를 다 1로 채워주었다.
• 이중 for문을 사용해서 2와 end사이의 인덱스에서 이들을 서로 곱해주면서 나오는 인덱스는 소수가 아니기 때문에 원소 값을 0으로 채워주었다.
• 마지막으로 start부터 end까지에 해당하는 범위에서 arr배열의 인덱스에 해당하는 원소가 1인 경우, 즉 소수인 경우 printf문을 사용해서 인덱스를 출력해주었다.