에라토스테네스의 체

문제설명

문제

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

입력

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

출력

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

접근

M이상 N이하의 숫자를 하나씩 자신보다 작은수로 나누어 소수를 확인하는 방법을 사용하면 시간초과가 난다. 에라토스테네스의 체 방식으로 구현해야 시간초과없이 통과할 수 있다.

에라토스테네스의 체(Sieve of Erathosthenes)

원리에 대한 자세한 설명은 맨 밑에 URL 참고하세요.

• 가장 작은 소수인 2부터 구하고자 하는 구간의 모든 수를 나열한다.
• 2는 소수이므로 2의 배수들은 모두 소수가 아니다. 따라서 2의 배수들은 모두 지운다.
• 3도 소수이므로 3의 배수들도 모두 소수가 아니다. 3의 배수들도 모두 지운다.
• 남은 수들 중에서 가장 작은 5는 소수이므로 5의 배수들도 소수가 아니다. 따라서 5의 배수들도 모두 지운다.
• 다음과 같은 방식으로 끝까지 반복한다.

코드

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

int main(){
    int m,n;
    cin >> m >> n;
    
    bool* isPrime = new bool[n+1];
    fill(isPrime, isPrime+n+1, true);
    isPrime[0] = isPrime[1] = false;
    
    for(int i=2; i<=n; i++){
    	if(isPrime[i]){
			int j=2;
			while(i*j <= n){
				isPrime[i*j] = false;
				j++;
			}	
		}
	}
	
	for(int i=m; i<n+1; i++){
		if(isPrime[i])
			cout << i << '\n';
	}	
}

참고

Wikipedia, Sieve of Eratosthenes
BOJ #1929

이 글이 도움이 되셨다면 추천 클릭을 부탁드립니다 :)