프로그래머스 (C/C++) 12921 : 소수 찾기

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

프로그래머스

---

풀이

에라토스테네스의 체 원리를 이용해서 풀었다.

에라토스테네스의 체란 소수를 찾는 방법으로, 간단히 설명하자면 어느 숫자가 소수로 판별되면 해당 소수의 배수를 모두 지우는 방식으로 소수를 판별하는 방식이다.

(밑의 동영상 참고)

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

 

 

+ 효율성 테스트

- n이 소수인지 구할 때 2~n의 값을 모두 나누지 않고, n보다 작은 소수로 나눴을 때 나눠지지 않는다면 n은 소수다.

  (n이 합성수라면 n보다 작은 소수들의 곱으로 나타낼 수 있으므로)

 

- n보다 작은 소수보다 sqrt(n)보다 작은 소수로만 나눠서 판별한다.

(아래 설명 참고)

소수 판별법, 왜 루트 N 이하의 수만 나눠보면 되는 것일까?

---

코드

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

using namespace std;

bool Num[1000001];
vector<int> Dec;

bool Is_dec(int n){
    for(auto i:Dec){
        if(i>sqrt(n)) return true;
        if(n%i == 0) return false;
    }
    return true;
}

int solution(int n) {
    int answer = n - 1;
    for(int i = 2; i <= n;i++){
        
        if(!Num[i] && Is_dec(i)){
            Dec.push_back(i);
            
            for(int j = 2*i; j <= n; j += i){
                if(!Num[j]) Num[j] = true, answer--;
            }
        }
        
    }
    return answer;
}