[프로그래머스]소수 찾기 / 에라토스테네스의 체 알고리즘

문제

 

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

 

풀이 1

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

using namespace std;


bool sosu(int n){
    for(int i=2; i<=sqrt(n);i++){
        if(n%i == 0) return false;
    }
    return true;
}

int solution(int n) {
    int answer = 1;
    for(int i=3; i<=n; i++){
        if(i%2==0) continue;
        if(sosu(i))answer++;
    }
    return answer;
}

효율성 0점이 나온 코드이다.

숫자 하나하나 for문을 통해 소수를 판별해야 했기 때문에, 정답을 구할 순 있었지만 효율성이 좋지 못했다.

 

 

 

풀이 2

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

using namespace std;

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

 

에라토스테네스의 체 를 이용한 풀이

이 방법으로 소수를 찾으려면, 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다.

 

 

출처 위키백과

첫 번째 코드의 시간 복잡도는 O(N^2)이지만, 

에라토스테네스의 체를 이용한 복잡도는 O(NloglogN)로 매우 효율적이다!

 

 

 

---

다른 사람 풀이

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<bool> tmp(n+1, true);

    for (int i=2; i<n+1; i++) {
        if (tmp[i] == true) {
            for (int j=2; i*j<n+1; j++) tmp[i*j] = false;
            answer++;
        }
    }

    return answer;
}

소수의 개수만 구하면 되는 문제였기 때문에, bool 벡터를 이용해 더 짧은 코드로 해결할 수 있었다.

 

 

 

 

---

https://donggoolosori.github.io/2020/10/16/eratos/

[Algorithm] 에라토스테네스의 체 - C++ - DGOS | 동꿀오소리

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전