프로그래머스 - 소수찾기 - C++

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

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

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

 

주어진 n까지의 수 중에서 소수가 몇개인지 찾는 문제이다.

기존에 적용했던 소수판별 알고리즘으로 접근했을 때 효율성 문제에서 시간초과가 떠서 실패했다. 

 

chatgpt에 검색결과 에라토스테네스의 체라는 개념을 알게되었다. 

작은 수부터 시작하여 그 수의 배수들을 전부 제거해나가는 방식으로 소수를 구하게 된다. 

 

조건이 i*i<=n 까지인 이유는 n=a*b 일때, 둘 중 하나는 반드시 루트 n 보다 작아야하기 때문이다. 

따라서 a를 찾으면 b는 자동으로 있는것이 되기 때문에 루트 n까지 약수가 없다면 그 수는 소수인 것이다. 

 

이 조건으로 2부터 시작하여 2의 배수, 3의배수를 차례로 지워나간다.

 이 때, 만약 arr[i]가 소수라면 i*i 부터 i의 배수를 전부 지워나가게 되는데 

왜 i*i 부터 시작인가하는 것이 의문이었다. 

 

i*i 이전의 i의 배수들은 이전의 소수의 배수로써 제거되었을 것이기 때문에 i*i부터 시작하는 것이 효율적인 선택이다. 

왜냐하면 i*i 이하의 i의 배수는 i가 5라고하면

2*i, 3*i, 4*i 이다. 따라서 i*i 가 지워지지않은 i의 배수중 가장 작은 배수이다. 

이렇게 전부 지우고 소수로서 true인 수들을 세면 해결이다.