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

그냥 기본적인 이중포문을 돌리면 정확성 테스트부터 시간초과가 난다.

 

풀이 1 (정확성 통과, 효율성 시간초과)

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 1;
    vector<int> prime = { 2 };

    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < prime.size(); j++) {
            if (i % prime[j] == 0) break;
            if (j == prime.size() - 1) {
                answer++;
                prime.push_back(i);
            }
        }
    }
    return answer;
}

 

나름 생각해서 해본 첫 시도. 소수를 찾아 추가할 때마다 소수 목록에 추가해 수를 소수로 나눴을 때 나누어 떨어지는지를 검사했다.

정확성 테스트는 성공했으나 효율성에서 시간초과가 난다.

 

그래서 수학적으로 다르게 접근해 재시도.

풀이 2 (정확성 통과, 효율성 시간초과)

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int solution(int n) {
    int answer = 1;
    vector<int> prime = { 2 };

    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < prime.size(); j++) {
            if (i % prime[j] == 0) break;
            if (j == prime.size() - 1) {
                answer++;
                prime.push_back(i);
            }
        }
    }

    return answer;
}

정확성 테스트에서 걸린 시간을 보니 나름 많이 시간 단축을 했지만,

효율성 테스트에서 다시 시간초과가 났다.

 

그래서 구글링해서 찾아온 다른 방법.

풀이 3 : 에라토스테네스의 체

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    int eratos[1000000] = { 0 };

    for (int i = 2; i <= n; i++) {
        if (eratos[i] == 0) {
            answer++;
            for (int j = 1; i * j <= n; j++) {
                eratos[i * j] = 1;
            }
        }
    }
    return answer;
}

 

개수가 적은 경우에는 1000000개를 검사해야 해서 시간이 늘어나지만,

1로 바꾼 배열들(이미 소수가 아니라고 판별된 수들)은 검사를 하지 않아서 개수가 많은 경우에는 더 효율적인 방법이다.

 

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<int> eratos;

    for (int i = 0; i <= n; i++) {
        eratos.push_back(0);
    }

    for (int i = 2; i <= n; i++) {
        if (eratos[i] == 0) {
            answer++;
            for (int j = 1; i * j <= n; j++) {
                eratos[i * j] = 1;
            }
        }
    }
    return answer;
}

 

쓰지 않는 배열 방까지 선언하는 것이 싫어 선언 방식을 바꿔봤다.

개수가 많아지면 push_back을 일일이 하면서 시간이 더 많이 드는 것 같지만, 일반적인 경우에는 더 빨라 보인다.

 

어려워....