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

#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
        // 에라토스테네스의 채 소수(true) 소수아님(false)
    vector<bool> arr(n+1, true);
    
    for(int i =2; i<=n;i++){
        if(arr[i] == true){
            answer++;
                // i를 제외한 i의 배수는 다 소수 아님
            for(int j =2; j*i <= n; j++){
                arr[j*i] = false;
            }
        }
    }
    return answer;
}

 

j <= sqrt(i)으로 for문을 돌리면서 i%j==0 인 경우를 제외하는 방식으로 소수를 찾으면 문제는 해결되지만 효율성 측면에서 시간초과가 발생한다.

 

따라서 "에라토스테네스의 채" 방식을 사용한다.

처음 모든 수를 소수라고 한다. 2, 3, 4, 5, 6,... 모두 소수이지만 2의 배수를 지우고 3의 배수, 5의 배수, i의 배수를 지우다보면 소수만 남게된다.

따로 for문을 돌려서 true인 경우를 찾지 않고 i의 배수를 지우는 과정에서 같이 카운팅해도 된다.