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

문제

소수 찾기 : 문제 링크

문제 분석

• 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 완성. 소수는 1과 자기 자신으로만 나누어지는 수를 의미한다. (1은 소수가 아니다.)

• 제한 조건

• n은 2이상 1000000이하의 자연수이다.

• 제한 조건의 범위가 크기 때문에 일반적인 소수 판별 방법으로 푸니 일부 효율성 테스트 케이스에서 시간을 초과했다. 따라서, 에라토스테네스의 체라는 알고리즘으로 해결했다. 간단히 말하면 loop 순회 중 소수를 찾으면, 그 소수의 배수를 모두 소수에서 배제하는 방식이다.
• 1부터 n 사이에 있는 소수의 개수를 저장할 정수형 변수 answer을 0으로 초기화. 제한 조건대로 정수형 벡터 v를 1000000의 크기로 0으로 초기화. for loop의 초기화식을 i = 2로 설정하여 n까지 순회하고, 배열 v의 인덱스 i 위치 원소가 0이라면 answer을 1씩 늘림. 이후, 또 다른 for loop를 통해 v중 해당 소수의 배수에 해당하는 인덱스 원소를 1로 저장. 따라서, 이후 순회중 1을 만나면 소수가 아니므로 소수의 개수에 반영하지 않음. 모든 loop 탈출 후, 최종적으로 저장된 answer을 return

풀이

#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<int> v(1000000, 0);
    
    for(int i = 2; i <= n; ++i) {
        if(v[i] == 0) {
            answer++;
            for(int j = 1; i * j <= n; ++j) {
                v[i * j] = 1;
            }
        }
    }
    return answer;
}