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

문제

---

문제를 보시려면 링크를 클릭해주세요.

풀이

---

소수 구하기 최적의 알고리즘인 에라토스테네스의 체를 이용하면 간단하게 풀 수 있습니다.

1. 주어진 숫자 크기의 배열을 만들어 모든 배수들을 체크해줍니다. (2의 배수, 3의 배수 …)

2. 체크된 수는 그 배수들도 이미 체크가 되어있기에 넘어가줍니다.

3. 최종적으로 체크 안된 수들이 소수임을 알 수 있습니다.

소스 코드

---

#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<bool> chk(n+1, 0);
  
    for(int i=2; i<=n; i++){
        if(chk[i])
            continue;
        
        for(int j=i+i; j<=n; j+=i){
            chk[j]=1;
        }
    }
    
    for(int i=2; i<=n; i++){
        if(!chk[i]){
            answer++;
        }
    }
    
    return answer;
}