[프로그래머스/Level 1] 소수 찾기 (C++)

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

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

 

풀이

인프런에서 비슷한 문제를 풀어본 적 있어서 다음과 같이 코드를 작성했는데 시간초과가 발생했다.

 

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

int solution(int n) {
    int cnt=0, flag;
    for(int i=2;i<=n;i++) {
        flag=1;
        for(int j=2;j<=sqrt(i);j++) {
            if(i%j==0) {
                flag=0;
                break;
            }
        }
        if(flag==1) cnt++;
    }
    return cnt;
}

입력 범위가 최대 1000000 이라서 제곱근을 이용해 절반으로 줄인다해도 시간초과가 발생하는 것 같았다. 그래서 도저히 방법을 모르겠어서 구글링한 결과, '에라토스테네스의 체' 라는 방법을 이용하여 문제를 해결할 수 있다는 사실을 알게되었다.

 

과정은 다음과 같다.

2일 때 소수의 개수를 하나 증가하고, 2의 배수를 모두 true로 체크한다.

3일 때 소수의 개수를 하나 증가하고, 3의 배수를 모두 true로 체크한다.

4일 때, true이므로 그대로 패스

5일 때 소수의 개수를 하나 증가하고, 5의 배수를 모두 true로 체크한다.

이러한 과정을 계속 반복하는 간단한 방법이다. ( 시간 복잡도는 O(NlogN) )

 

전체 코드

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

int solution(int n) {
    int res=0;
    bool eratos[n+1];
    memset(eratos,false,sizeof(eratos));
    for(int i=2;i<=n;i++) {
        if(!eratos[i]) {
            res++;
        }
        for(int j=i;j<=n;j+=i) {
            eratos[j]=true;
        }
    }
    return res;
}