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

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

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

특정 수까지의 소수의 개수를 찾아서 리턴하는 문제입니다.

 

처음에는 반복문으로 소수인지 체크를 해서 개수를 증가시키는 방향으로 갔었는데, 테스트케이스와 효율성 검사에서 특정 문제들에서 시간 초과 등의 문제가 있었습니다.

 

그래서 검색하다가 알아본 방법이 바로 에라토스테네스의 체 입니다.

 

쉽게 말해서 수를 일렬로 쭉 세워놓은 후, 앞에서부터 특정 숫자의 배수를 제거하는 방법입니다.

 

2,3,4,5,6,7,8,9,10 이렇게 수가 나열되어 있다고 할 때,

처음 나오는 2를 제외한 2의 배수를 모두 제거합니다. -> 2,3,5,7,9

그 다음 나오는 3을 제외한 3의 배수를 모두 제거합니다 -> 2,3,5,7

이 방식으로 특정 숫자까지 반복하면 결국 남는 숫자는 소수라는 것이 에라토스테네스의 체 입니다.

 

이 방법을 사용하자마자 시간이 엄청나게 줄어들었습니다. 막 20초로 겨우 통과하던 문제가 2초,3초대로 바뀌는...!!

 

검색안하고 억지로 풀려고 했던 거 반성합니다.... 바퀴를 창조하지 말아야지..

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<int> arr;
    
    for(int i = 0; i<=n; i++)
    {
        arr.push_back(i);       // 벡터 초기화
    }
    
    for(int j=2; j<=n; j++)
    {
        if(arr[j] != 0)     // 0이 아니면 -> 소수라면
        {
            answer++;       // 소수 확인
            for(int k = j; k <= n; k = k + j)   // 그 수의 배수 전부 다 0으로 처리
            {
                arr[k] = 0;
            }
        }
    }
    
    return answer;
}