[CS]에라토스테네스의 체

에라토스테네스의 체

• 에라토스테네스라는 뭐시깽이가 만든 소수 판별 알고리즘
• 개념(쉽다!): 소수의 배수 != 소수

1. bool 벡터를 만들고, true로 초기화해준다.
2. 0과 1은 소수가 아니므로, false로 초기화한다.
3. for문을 돌며, 소수를 체크한다.
   3-1. 소수는 제곱으로 판별한다.
4. 현재 수(i)에 따라 진행한다.
   4-1. 소수가 아닌 경우 다음 반복을 실행한다.
   4-2. 소수인 경우 현재 수(i)의 배수가 소수가 아님을 체크한다.
   

에라토스테네스 알고리즘

vector<bool> prime(MAX, true);
void eratoss(){
    prime[0] = false;
    prime[1] = false;
    for(int i = 2; i*i <= MAX; ++i){
        if(!prime[i]) continue;
        for(int j = 2*i; j <= MAX; j += i){
            prime[j] = false;
        }
    }
}