[ 백준 1929 ] 소수 구하기 (C++, 에라토스테네스의 체)

[문제보기]

 

[해결과정]

 에라토스테네스의 체 사용

-> 각 해당하는 수가 소수가 아닐 경우 그에 대한 배수는 모두 소수 처리하는 것

 

[소스코드]

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

int n, m;
int prime[1000005]={0,1,0,};

void isPrime(){
    for(int i=2; i<=m; i++){
        if(prime[i]==0){
            for(int j=2; i*j <=m; j++) prime[j*i]=1;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    isPrime();
    
    for(int i=n; i<=m; i++) if(prime[i]==0) cout << i <<"\n";
    
    return 0;
}

 

[해결 과정 중 실수한 부분 / 잡담]

 없음

 

[관련 문제 혹은 비슷한 문제]

 없음