[Programmers] Level 1. 소수의 합 (C++)

정리

소수를 구하는 문제였다.
소수를 구하는 방법 중 가장 많이 알려져있는 알고리즘은 에라토르테네스의 체 다.

에라토스테네스의 체를 간단하게 설명해보면,
2부터 시작한다. 그리고 2부터 자신을 제외한 자신의 배수를 제거한다.
2를 제외한 2의 배수를 제거하고,
3을 제외한 3의 배수를 제거하고,
4는 2의 배수이기 때문에 이미 제거가 되어있다. 이미 제거가 되어있는 수들은 건너뛰고 진행한다.
위와 같은 과정을 반복하면 남아있는 숫자는 소수가 될 것이다.

따라서, 에라토스테네스의 체를 이용해서 풀면 쉽게 풀 수 있는 문제였다.

소스 코드

#include <vector>

using namespace std;

long long solution(int N) {
    long long answer = 0;
    vector<long long> m;
    
    for(int i=0; i<=N; i++){
        m.push_back(i); // vector에 숫자를 넣어준다.
    }
    
    for(int i=2; i<=N; i++){
        if(m[i] == 0) continue; // 전의 숫자의 배수인 경우 0이기 때문에 건너뛴다.
        for(int j=i+i; j<=N; j+=i){ // 자기 자신을 제외한 배수를 구해서 0으로 만든다.
            m[j] = 0;
        }
    }
    
    for(int i=2; i<=N; i++){
        if(m[i] != 0) answer += m[i];
    }
    
    return answer;
}