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

1. 문제 설명

1부터 입력으로 받는 n 사이에 있는 소수의 개수를 반환하는 문제

2. 풀이

#include <string>
#include <vector>

using namespace std;

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

3. 해설

이중 for문으로 1씩 증가시켜가며 한 번도 나누어지지 않는 경우 카운트를 증가시키는 로직으로는 실행시간 초과가 뜬다...

그래서 에라토스테네스의 체라는 알고리즘을 사용해서 시간복잡도를 줄였다.

에라토스테네스의 체라는 알고리즘은 소수 찾기 문제를 다음과 같이 접근한다.

 

기본적으로 에라토스테네스의 체는 배수를 기반으로 접근한다.

1. 가장 작은 소수인 2부터 시작한다.
2. 2의 배수인 수들은 소수가 아니므로 리스트에서 제거한다.
3. n까지 배수 판정을 하고 나면, 남아 있는 수들 중 가장 작은 수부터 다시 배수 판정을 반복한다.
4. 최종적으로 남아있는 수들이 소수이다.

코드에서는 bool 형 vector의 인덱스와 동일시 되는 숫자가 소수인지 아닌지를 저장해서 판단한다.

위 과정을 시각화한 모습 (출처 : 위키백과)