백준 1929 소수 구하기(에라토스테네스의 체)

https://www.acmicpc.net/problem/1929

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 에라토스테네스의 체를 이용하여 소수를 구하는 문제입니다. 시간 제한이 있기 때문에 단순히 소수를 구하는 방법으로는 풀 수 없습니다.

 

에라토스테네스의 체란 어떤수 이하에 있는 모든 소수를 구해야 할 때 2의 배수를 모두 제거하고 그다음 3의 배수를 모두 제거하고 그다음 5의 배수를 모두 제거하는 방법으로 소수들을 골라내는 방법입니다. bool 배열을 통하여 구현을 하였습니다.

 

다음은 코드입니다.

 

#include <iostream>
//에라토스테네스의 체 

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int M,N;
	bool arr[1000001];
	fill_n(arr, 1000001, true);
	arr[0] = false; //0과 1인 경우는 소수가 아니다 
	arr[1] = false; 
	cin >> M >> N;
	for(int i =2; i <= N; i++) {//2인경우 부터 차례대로 배수에 해당하는 수를 false로 바꿈 
			if(arr[i]) {
				for(int j = i+i; j <= N; j+=i)
					arr[j] = false;
			}
				
		}
	
	for(int i = M; i <= N; i++)
		if(arr[i])
			cout<<i<<'\n';
	
	return 0;
}