프로그래머스 사용자 제작 문제 > 소수의 합

https://programmers.co.kr/learn/courses/30/lessons/14406

1. 문제

소수 판별 알고리즘 소수의 합을 구하는 문제

2. 알고리즘

키워드 - 소수 판별법, 에라토스테네스의 체

3. 코드

#include <iostream>
#include <vector>
 
using namespace std;
 
long long solution(int N) {
    long long answer = 0;
    
    vector<long long> arr(N+1, 0);
    
    for (int i = 2; i <= N; i++) {
        arr[i] = i;
    }
 
    for (int i = 2; i <= N; i++) { 
        if (arr[i] == 0) // 이미 체크된 수의 배수는 확인하지 않는다
            continue;
 
        // i를 제외한 i의 배수들은 0으로 체크
        for (int j = i + i; j <= N; j += i) {
            arr[j] = 0;
        }
    }
 
    // 프린트 확인용
    for (int i = 2; i <= N; i++) {
        if (arr[i] != 0)
            answer = answer + arr[i];
            //cout << arr[i] << " ";
    }
    return answer;
}