프로그래머스 - 소수 찾기

프로그래머스 - 소수 찾기

에라토네세의체를 쓰면 특정 구간 내에서 소수의 개수를 빠르게 구할 수 있다.
n까지 모두 구하지 않고 k*k > n이 되는 k에서 break를 걸거나, 배수를 지우는 로직에서 최적화를 수행할 수 있다.

코드는 다음과 같다.

#include <string>
#include <vector>

using namespace std;

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

// k*k가 n을 넘는 경우 break
#include <string>
#include <vector>

using namespace std;

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

// 배수를 지울 때, j = i*2가 아닌 i*i부터 시작
// i*2는 2의 배수, i*3은 3의 배수, i*(i-1)은 i-1의 배수로 이미 지워졌기 때문에 i*i부터 시작해도 됨
#include <string>
#include <vector>

using namespace std;

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