[BOJ_C] 1929번

- 문제

1929번 문제

 

- 풀이

#include <stdio.h>
#include <stdlib.h>

int main(){
    int m, n;
    scanf("%d %d",&m, &n);

    int* prime = (int*)malloc(sizeof(int)*(n+1));
    for(int i=0; i<=n; i++)
        prime[i] = 0;
    prime[0] = 1, prime[1] = 1;

    for(int i=2; i<=n; i++){
        if(!prime[i]){
            for(int j=2; i*j<=n; j++){
                 prime[i*j] = 1;            
            }

        }
    }

    for(int i=m; i<=n; i++)
        if(!prime[i])
            printf("%d\n", i);

    return 0;
}

 

문제에서 m에서 n사이의 소수를 모두 출력하라 했으므로, n+1만큼 prime이라는 배열을 만들고 0으로 초기화한다. (이때 n+1만큼 만들어주는 이유는 소수를 출력할 때 조금 더 편하게 하기 위해서 이다. 별로 큰 뜻은 없음.) 그 뒤, 소수에 포함되지 않는 0과 1을 소수가 아니라는 뜻으로 1을 대입해 준다. 앞으로 소수가 아닌 수엔 1을 대입하여 표시할 것이다.(일종의 플래그) 

이제 준비과정은 끝났다. 본격적으로 소수를 구할 것인데, 2부터 n까지 prime[i]가 소수라면 i*j가 n과 같거나 작을 때 까지 해당 수의 자리에 1을 넣어 소수가 아니라는 것을 표시한다. 이를 i가 n보다 커질 때까지 반복하면 소수는 0으로 소수가 아닌 수는 1으로 표시되어 있을 것이다. 

마지막으로 m과 n사이의 소수인 수 즉, prime[i]가 0을 가지는 수를 출력해주면 된다.

 

- 실행결과

실행결과