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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

에라토스테네스의 체를 이용하여 소수를 미리 체크해두고 1 ~ n 사이의 범위 내에 소수의 개수를 체크하여 해결하였다.

에라토스테네스의 체를 모른다면 에라토스테네스의 체 포스트를 읽어보자.

코드

#include <string>
#include <vector>

using namespace std;

vector<bool> prime;

void precalc(vector<bool>& prime, int n){
    prime[1] = false;
    for(int i=2; i*i<=n; i++){
        if(prime[i] == true)
        for(int j=i*i; j<=n; j+=i){
            if(prime[j] == true) prime[j] = false;
        }
    }
}

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