[C++] 소수 판정(에라토스테네스의 체)

숫자들 중 소수인 것들을 어떻게 구분할 수 있을까?

 

 

0. 충분히 큰 수를 최댓값으로 설정한다.

 

1. int형 배열을 하나 만든 뒤, 각 값들을 각 인덱스로 초기화한다.

 

2. 소수인 2부터 시작해서 배수들을 모두 0으로 초기화한다.

※이때, 소수들은 초기화해선 안되므로 bool형 변수를 활용한다.

 

3. 배열에 0이 아닌 숫자들이 들어있는 숫자들은 모두 소수이다!

 

#include <iostream>
#define MAX 1000000
using namespace std;

int num[MAX];

int main(){
    for(int i = 2; i <= MAX; i++){
		num[i] = i;
	}

	for(int i = 2; i <= MAX; i++){
		bool flag = false;
		for(int j = i; j <= MAX; j += i){
			if(flag == false){
				flag = true;
				continue;
			}else{
				num[j] = 0;
			}
		}
	}

    for(int i = 1; i <= 1000; i++){
        if(num[i] != 0) cout<<num[i]<<"\n";
    }
    
    return 0;
}

 

출력

2
3
5
7
11
...