C++:: 프로그래머스 < 소수 찾기 >

에라토스테네스의 체를 사용하여 소수를 구해 풀면 간단한 문제이다.

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

int solution(int n) {
    int answer = 0;
    vector<bool> era(n+1, true);
    for (int i=2; i*i<=n; i++) {
        if (era[i]) {
            for (int j=i*i; j<=n; j+=i) {
                era[j] = false;
            }
        }
    }
    for (int i=2; i<=n; i++) if (era[i]) answer++;
    return answer;
}