소수 찾기

들어가는 말

1부터 n까지 범위의 소수 갯수를 반환하면 되는 문제다. 1은 소수가 아니니 제외한다.

코드 설명

소수 찾는 문제는 에라토스테네스의 체를 사용하면 쉬이 풀 수 있다는 걸 알아냈다. 에라토스테네스의 체는 어떤 수의 배수이면 소수가 아닌 아이디어에서 나왔다. 즉, 4는 2의 배수이므로 소수가 아니다.
에라토스테네스의 체는 다른 글에서 더 자세하게 설명하겠다.

코드

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int solution(int n) {
    //에라토스테네스의 체를 사용한다.
    /*1을 제외한 수의 배수가 되는 수는 소수가 아니다라는 아이디어에서 나옴.*/
    
    vector<int> v;
    int answer = 0;
    
    for(int i = 0; i <= n; i++){
        v.push_back(i);
    }
    
    for(int i = 2; i <= sqrt(n); i++){
        if(v[i] == 0){
            continue;
        }
        
        for(int j = i * i; j <= n; j = j + i){
            v[j] = 0;
        }
    }
    
    for(int i = 2; i <= n; i++){
        if(v[i] != 0){
            answer++;
        }
    }
    return answer;
}