에라토스테네스의 체

Sieve of Eratosthenes

고대 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법으로, 체로 치듯이 수를 걸러낸다고 하여 에라토스테네스의 '체'라고 부른다.

숫자 2부터 시작하여 현재 수의 배수가 되는 숫자들을 모두 제외해 나가는 간단한 방법이다.

C++

void eratos(){
    vector<bool> prime(100, true);
    prime[1] = false;
    for(int i = 2; i <= 100; i++){
        if(prime[i]){
            for(int j = i+i; j <= 100; j += i){
                prime[j] = false;
            }
        }
    }
}

1부터 100까지 모두 true 로 초기화한 후 소수가 아닌 수들을 false 로 바꾸어 나간다.