C++ / 프로그래머스 / 소수 찾기

문제

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

코딩테스트 연습 - 소수 찾기

문제풀이

에라토스테네스의 체를 이용하여 구했다.

n크기만큼의 bool형태 벡터를 만들고 모두 true로 둔다.

idx는 1은 소수가 아니므로 2부터 n의 제곱근 값까지 돌면서 n까지 idx의 배수들을 false로 바꾼다.

2부터 n까지 돌면서 true값이 있으면 answer++를 해준다.

 

코드

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

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<bool>check(n+1, true);    
    int idx = 0, idx2 = 0;
    for (idx = 2; idx <= sqrt(n); ++idx)        
        for (idx2 = 2; idx*idx2 <= n; ++idx2)
            check[idx * idx2] = false;            
    
    for (idx = 2; idx <= n;++idx)
        if (check[idx] == true) answer++;
    return answer;
}