[알고리즘] 소수판별

💡 소수 Prime Number

    1보다 큰 정수 p의 양의 약수가 1과 p뿐일 때 p를 소수라고 하며 1보다 큰 정수 n이 소수가 아닐 때 n을 합성수(Composite number)라고 한다.

💡 관련문제: 프로그래머스 Level 1 소수 찾기

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

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

첫번째 시도

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

using namespace std;

int solution(int n) {
    int answer = 1;
    int sq;
    int div;   

    sq = ceil(sqrt(n));  

    for(int i=3;i<=n;i++) {
        div = (i>=sq) ? sq : i;
        for(int j=2;j<div;j++) {
            if(i%j==0) {
                break;
            } else if(j==div-1) {
                answer++;
            }
        }
    }    
    return answer;
}

=> 시간 초과

두 번째 시도

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

using namespace std;

int solution(int n) {
    int answer = 1;
    int div;
    vector<int> v;
    
    v.push_back(2);
    
    for(int i=3;i<=n;i++) {
        if(i%2!=0) {
            v.push_back(i);
        }
    }
    
    div = ceil(sqrt(n));
    
    for(int i=2;i<=div;i++) {
        for(int j=2;j<v.size();j++) {
            if(v.at(j)%i==0 && v.at(j)/i!=1) {
                v.erase(v.begin()+j);
            }
        }
    }
    
    answer = v.size();
    
    return answer;
}

=> 시간 초과

세 번째 시도

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

using namespace std;

int solution(int n) {
    int answer = 0;
    int div = ceil(sqrt(n));
    vector <int> arr;
    
    for(int i=1;i<=n;i++) {
        arr.push_back(i);
    }
    
    arr[0] = 0;
     
    for(int i=2; i<=div; i++){
        if(arr[i-1]){
            for(int j = i * i; j <= n; j += i)
                arr[j-1] = 0;
        }
    }
             
    for(int i = 0; i < n; i++){
        if(arr[i]!=0) {
            answer++;
        }
    }
    
    return answer;
}

=> 에라토스테네스의 체

💡 하나씩 나눠보기

    단일 숫자의 소수 여부 판별 시 유용

1. 2를 제외한 짝수는 제외
2. √n까지 나눠보기
   =>O(√n)

💡 에라토스테네스의 체

   대량의 소수를 한 번에 판별할 때 유용

1. 배열을 생성하여 초기화한다.
2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
3. 2부터 시작하여 남아있는 수를 모두 출력한다.