에라토스테네스의 체란? (feat.cpp 구현)

목차

• 소수 란?
• 에라토스테네스의 체

소수 란?

 

1과 자기 자신을 제외한 나누어지는 수가 없는 수를 말합니다.

그렇게 되면 2를 제외한 모든 짝수는 소수가 될 수 없습니다.

(짝수들은 2로 나누어 떨어지기 때문입니다.)

 

bool check_the_prime_number(int num){
	// 1, 2를 제외한 모든 짝수는 소수가 아니다.(false 반환)
    if(num == 2) return true;
    if(num == 1) return false;
    if(num % 2 == 2) return false;
    
    // n-1의 수까지 나누어 보고 나누어 떨어질시 소수 아님 판정(false)
    for(int i = 3; i < num; ++i){
    	if(num % i == 0) return false;
    }
    
    return true;
}

 

에라토스테네스의 체

 

위의 방식에서 효율적으로 소수를 찾는 방법이 에라토스테네스 체의 방법입니다.

n이라는 숫자 안에 소수가 무엇이 존재하는지 알고 싶은 경우

2... n까지의 숫자를 종이에 적은 후 자기 자신을 제외한 배수들을 하나씩 지웁니다.

 

1. 2를 제외한 2의 배수들을 지워줍니다.

2를 제외한 2의 배수를 지운모습

2. 다음 수중 지워지지 않은 수(3)의 배수들을 지워줍니다.

3을 제외한 3의 배수들을 지운 모습

1, 2의 과정을 n번째까지 진행합니다.

 

결과적으로 남은 수들은 소수가 됩니다.

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

vector<bool> solution(int n){
	// n + 1만큼의 bool 배열 (소수인지 아닌지 체크용)
	// false : 소수 / true : 소수가 아님
    vector<bool> checked(n + 1, false);
    
    checked[0] = true;
    checked[1] = true;
    
    for(int i = 2; i < sqrt(n); ++i){
    	if(!checked[i]){
        	// 소수가 아닐경우 
            // i의 배수인 수들을 지워준다(true)
            for(int j = i * 2; j < n; j+=i){
            	checked[j] = true;
            }
        }
    }
    
    return checked;
}