1929번: 소수 구하기

문제:

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

입력:

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

풀이:

• 우선 이 문제는 최대 범위가 1,000,000이 되므로 소수를 판별 해야 되는 범위가 상당히 광범위하다. 따라서 시간 초과를 안받기 위해서는 에라토스테네스의 체 알고리즘을 구현하여야 된다.
• 에라토스테네스의 체 알고리즘은 소수인지 아닌지 판별해주는 표를 만드는 알고리즘이라고 생각하면 된다. 그 결과로 나온 배열은 소수인지 아닌 판별해주는 표가 된다고 생각하면 된다.
• 배열을 통해서 해당 인덱스 값이 소수인지 아닌지 판별해주도록 하는 알고리즘이라고 생각하면 편하다. 예를 들면 prime[100]이라는 배열이 있다면 prime[10]을 넣었을 때 10이 소수인지 아닌지 판별 해주는 알고리즘이라고 생각하면 된다. 따라서 배열에 저장 되는 값은 1(true), 0(false)면 충분하다.
  1. 해당 알고리즘을 구현하기 위해서는 0번째와 1번째 값을 제외한 모든 값을 for문으로든 memset()과 같은 방식으로 true로 초기화 해줘야 된다(0과 1은 소수가 아니기 때문에 미리 false로 초기화 해야 된다).
  2. 이제 모든 수마다 max 값까지 배수는 false로 바꿔줄 것이다. 만약에 이미 false로 바꿔준 경우에는 배수도 이미 false로 되어 있을 것이므로 건너뛰어 준다. 이 for문 같은 경우는 처음에 연산 해야될 것들이 많지만 가면 갈 수록 점점 미리 false로 해놓은 값들이 많아서 점점 스킵 되는 값들이 많아진다. 따라서 연산하는데 초반에는 O(N^2)의 시간이 걸리다가 점점 O(N)에 수렴한다.
  3. 마지막으로 소수로 걸러낸 체에서 소수인 경우 인덱스 값을 출력해준다.

🔍 에라토스테네스의 체 알고리즘이 효율적인 이유는 숫자가 들어올 때마다 소수인지 연산을 안하고 이미 연산 된 배열에서 맞는지 아닌지만 return 해주어서 그렇다. 어떻게 보면 다음 장에서 다룰 다이내믹 프로그래밍의 일종이라고 할 수 있을 것 같다.

코드:

#include <iostream>

using namespace std;

bool prime[1000001] = {false, false}; //0과 1은 소수가 아니므로 false로 초기화 

int main(){
	int min, max;
	//입력 
	cin >> min >> max;
	//에라토스테네스의 체 구현 
	for(int i = 2; i <= max; i++) prime[i] = true;  //모든 배열 값 true로 초기화 
	for(int i = 2; i <= max; i++){
		 //이미 false로 바뀐 수는 무시 
		if(prime[i] == false) continue;
		//2부터 max까지 모든 배수 인덱스를 가진 값을 0으로 바꿈 
		for(int j = i+i; j <= max; j+=i) prime[j] = false;
	}
	//출력 
	for(int i = min; i <= max; i++){
		//소수인 경우에 인덱스 값 출력 
		if(prime[i]) cout << i << '\\n';
	}
}