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

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

1.문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

제한 조건

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

입출력 예

n	result
10	4
5	3

 

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

 

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

2.문제 풀이

• 소수를 판별하는 알고리즘을 작성한다.
• 소수 알고리즘으로 2부터 숫자 n사이의 소수 갯수를 리턴한다.

처음 내가 시도했던 방법은 시간 초과가 되지 않도록 isPrime함수에서 소수를 판별할때 n의 제곱근까지만 판단하도록 했다.하지만 이방법은 테스트 케이스에서 시간 초과가 뜨진 않았지만 효율성 테스트에서 실패하게 된다.

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

bool isPrime(int n)
{
    if(n < 2)
        return false;
    for(int i=2; i<=sqrt(n); ++i)
    {
        if(n % i == 0)
            return false;
    }
    
    return true;
}

int solution(int n) {
    int answer = 0;
    
    for(int i=1; i<=n; i++)
    {
        if(isPrime(i))
            ++answer;
    }
    return answer;
}

해당 문제를 해결하기 위해 찾아본 결과 소수를 찾는 알고리즘중 가장 시간 복잡도가 작은 알고리즘인 에라토스테네스의 체 알고리즘을 알게 되었다.

3. 에라토스테네스의 체

에라토스테네스의 체는 주어진 범위내에서 소수의 갯수를 빠르게 찾는 알고리즘으로 소수를 판별해야 하는 문제에서 자주 사용되는 알고리즘이다. 에라토스테네스의 체 알고리즘 구현방식은 다음과 같다.

1. 구하고자 하는 소수의 범위만큼 배열을 생성한다.

2. 2부터 시작되는 반복문안에서 현재 숫자가 소수라면 배수에 해당하는 수를 전부 소수가 아니라고 판단한다.

3. 구하고자 하는 범위의 배열 끝까지 2번을 반복해서 탐색하면 소수의 갯수를 찾아낼 수 있다.

이 방법은 소수를 기준으로 해당수의 배수들은 전부 소수를 약수로 가지기 때문에 배수에 해당하는 수를 소수가 아니라고 판단하는 것이다. 아래는 이해를 돕기위한 그림이다.  

 

출처: 위키백과 (에라토스테네스의 체)

4. 소스코드

#include <string>
#include <vector>

using namespace std;

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