[알고리즘 - 기초] 에라토스테네스의 체, 소수 구하기

에라토스테네스의 체란?

---

에라토스테네스의 체란 소수를 판별할 때 사용하는 알고리즘으로 고대 그리스 수학자 에라토스테네스가 발견했다.

여기서 말하는 소수란, 1과 자기 자신만을 약수로 가지는 수를 말한다.

 

 

에라토스테네스의 체 원리

---

1) 아래 그림과 같이 1에서 100까지의 수가 있다.

 

 

2) 1은 소수가 아니기 때문에 제외하고 2부터 생각해보자. 2는 소수에 해당하기 때문에 소수임을 체크해주고 2의 배수들은 소수가 아니기 때문에 제외시킨다.

 

 

3) 그다음 수인 3을 보면 제외되지 않았기 때문에 소수이다. 그리고 3의 배수를 모두 제외시킨다.

 

 

4) 그다음 수인 4는 제외됐으므로 5를 확인한다. 5는 제외되지 않았기 때문에 소수이다. 5의 배수까지 모두 제외시키면 아래와 같다.

 

 

5) 이렇게 계속해서 반복하다 보면 아래와 같은 결과를 얻을 수 있다.

 

 

 

소수 구하기

---

C++

#include <iostream>
using namespace std;

int main(){
    int is_prime[101];               // 100개의 수를 검사한다.

    for(int i = 0; i < 101; i++){
        is_prime[i] = i;
    }

    for(int i = 2; i < 101; i++){
        if(is_prime[i] == 0) continue;      // 이미 소수가 아니라면 넘긴다

        cout << i << " ";                   // 소수라면 출력해준다.

        for(int j = i * 2; j < 101; j+=i){      // 소수의 배수들을 모두 제거해준다.
            is_prime[j] = 0;
        }
    }

    return 0;
}

 

 

시간복잡도

---

O(NloglogN)

 

 

예제로 알아보는 에라토스테네스의 체

---

지금까지 배웠던 에라토스테네스의 체를 아래 문제에 적용시켜보자

 

1929번: 소수 구하기

 

[Solution]

[BOJ] 1929번: 소수 구하기 (C, C++, Java, Python3)