[BOJ/백준] 1929번 : 소수 구하기 (C++)

[BOJ/백준] 1929번 : 소수 구하기

BOJ 1747

문제 해석

• 두 숫자 사이에 소수를 출력하는 문제이다. 에라토스테네스의 체를 사용하면 금방 풀리는 문제이다.

에라토스테네스의 체

풀이

• 크기가 N+1인 배열을 선언한 후 값은 각각 인덱스로 채운다.
• 1은 소수가 아니므로 2부터 시작, 2부터 N 제곱근까지 탐색한다. 값이 인덱스이면 그대로 두고 , 그 값의 배수를 탐색해 0으로 변경시킨다.
• 남아있는 수 중에서 M이상 N이하의 수를 출력한다.

코드

#include <iostream>
#include <vector>
using namespace std;

int main(void){
    int M, N;
    cin>>M>>N;

    vector<bool> isPrime(N+1, true);
    isPrime[0] = isPrime[1] = false;

    for(int i=2; i*i<=N; ++i){//제곱근까지만 탐색 i<=sqrt(N); 해도됨
        if(isPrime[i]){
            for(int j=i*i; j<N+1; j+=i){
                if(j%i==0){//배수이면
                    isPrime[j]=false;//false(소수 아님을 의미)
                }
            }
        }
    }

    for(int i=M; i<=N; ++i){
        if(isPrime[i]){//true만 출력 (true == 소수)
            cout<<i<<'\n';
        }
    }
}