[C언어] 백준 1929번. 소수 구하기.

백준(BEAKJOON) |  단계별로 풀어보기

9-4단계 #1929번

 

www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 

문제 |

 

 

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

 

 

입력 |

 

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

 

 

출력 |

 

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

 

 

 

 

🥕 이 문제도 4948번 문제와 같이 에라토스테네스의 체를 이용하여 풀었다. 

 

 

<에라토스테네스의 체>

 

1.  n=2부터 n의 배수인 숫자들을 모두 지운다. (자기 자신은 지우지 않는다.)

 

2. 이미 지워진 숫자는 건너뛴다. (배열을 생성하여 판별)

 

예) 2의 배수인 4는 이미 앞에서 지워졌으므로 4의 배수들도 모두 이미 앞에서 지워진 상태이다. 따라서 건너뛴다.

 

3. n=2부터 지워지지 않고 남아있는 숫자들이 소수에 해당

 

 

이를 바탕으로 문제를 풀어보면, 처음에 소수를 판별할 배열을 하나 생성하고 0으로 초기화한다. ( 풀이에서는 num[246913] = {0,} )

이중 반복문을 통해 먼저 2번 과정을 시작한다. i= 2부터 i의 배수인 j 숫자들을 모두 지우는 것이다.(num[j]= 1) 이를 i가 2일 때부터 i가 n부터 작거나 같을 때까지 반복한다. i= 2부터 i가 n부터 작거나 같을 때, num[i]==0이면 이때의 i는 소수이다. 따라서 i를 출력한다.

 

 

 

 

-코드 첨부-

 

 

C언어

 

#include <stdio.h>
 
int main(void)
{
    //에라토스테네스의 체
    int n, m;
    int num[1000001]={0,};
    num[1]=1;
    scanf("%d %d", &m, &n);
    for(int i=2; i<=n; i++){
        if(num[i]==1){
            continue;
        }
        for(int j=i*i; j<=n; j+=i){
            if(j%i==0){
                num[j]=1;
            }
        }
    }
    for(int i=m; i<=n; i++){
        if(num[i]==0){
            printf("%d\n", i);
        }
    }
    return 0;
}