[알고리즘] 에라토스테네스의 체

소수 찾기 문제를 풀고 기왕 포스트하는김에 이론정리를 해놓는게 낫겠다는 생각이 들어서 정리하였다.

소수를 찾는 알고리즘이다.

위의 동영상처럼 1부터 N까지 숫자를 순회하며 순회한 수들의 배수를 제거하는 방법이다.

구체적인 구현 방법은 코드를 살펴보자

n을 입력받아서 1~n까지의 숫자 중에서 소수인 숫자를 출력하는 코드이다.

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

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

int main(){
    int n;
    cin >> n;
    vector<bool> prime(n+1, true);
    precalc(prime, n);
    for(int i=1; i<=n; i++){
        if(prime[i] == true)
            cout << i << ' ' << 는 소수입니다 << endl;
    }
    return 0;
}