[알고리즘] 에라토스테네스의 체(소수 구하기) - C++

에라토스테네스의 체는 소수를 구하기 위해 사용되는 알고리즘이다. 

 

시간 복잡도는 O(N^1/2) 이다.

 

만약 1~100 사이의 소수를 구한다고 한다면 에라토스테네스의 체는 이렇게 작동한다.

 

1. 배열에 1~100의 숫자를 채워 넣는다.

2. 2를 제외한 2의 배수들을 모두 지운다.

3. 위와 같이 자신을 제외한 모든 수의 배수들을 지운다.

4. 이 과정을 끝까지 반복하면 약수가 1과 자기 자신뿐인 소수만 배열에 남게 된다.

 

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

int main() {
    int n = 100;
    vector<bool> v(n + 1, 1);

    for (int i = 2; i * i <= n; i++) {
        if (v[i]) {
            for (int k = i * i; k <= n; k += i) {
                v[k] = 0;
            }
        }
    }
    
    for (int i = 2; i < v.size(); i++) {
        if(v[i]) cout << i << " ";
    }
}

C++ 로 구현해본 1~100까지 소수를 모두 구하는 코드이다.

구현하며 int vector로 처음부터 그 숫자를 가지고 하는것보다 bool을 이용하면 초기화하는 과정이 편할거같아 bool을 이용하였다. 

 

 

처음에 100만큼의 bool vector 값을 true로 초기화해주었고 그  뒤 i^2가 100 이하일때까지 for문을 돌려 주었다. 이게 i^2가 100보다 큰 i는 체크를 해도 의미가 없기 때문에 i^2가 n을 넘지 않을 때까지만 체크해주면 된다.

 

마지막으로 for문으로 bool vector를 체크하며 v[i]가 true인 경우는 소수이기 때문에 그때의 n값을 출력하여 주면 100 이하의 소수를 모두 출력할 수 있다.