[프로그래머스 Lv1] - 소수 찾기

20 May 2021

Reading time ~1 minute

소수 찾기

문제 해결 포인트

에라토스테네스의 체
- 2의 배수 다 지우고…
- 3의 배수 다 지우고…
- 이렇게 반복적으로 연관된 내용들을 같이 지우기 위해서 bool map을 사용한다!

#include <string>
#include <vector>

using namespace std;

vector<int> Erato(int n){
    bool arr[n+1];
    for(int i=1; i<=n; i++){
        arr[i] = false;
    }
    arr[0] = arr[1] = true;
    
    vector<int> prime;
    for(int i=2; i<=n; i++){
        if(arr[i]){ // 소수가 아니면 continue;
            continue;
        }
        prime.push_back(i);
        for(int j=i * 2; j<=n; j+=i){
            arr[j] = true;
        }
    }
    return prime;
}

int solution(int n) {
    int answer = 0;
    vector<int> prime = Erato(n);
    
    answer = prime.size();
    return answer;
}