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

문제 링크

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

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

---

C++ 풀이

#include <string>
#include <vector>
using namespace std;

int solution(int n) {
    int answer = 0;
    vector <bool> numbers(n + 1, true); //소수 확인을 위한 벡터
    for (int i = 2; i <= n; i++) {
        if (numbers[i] == true) {
            answer++;
            for (int j = (2 * i); j <= n; j += i) //찾은 소수의 배수들은 다 목록에서 제외
                numbers[j] = false;
       }
    }
    return answer;
}

2부터 시작하여 수가 소수인 경우(어떤 수의 배수이지 않아서 제외되지 않은 경우), 해당 수를 카운트해주고 해당 수의 배수들을 다 제외 처리한다.