[Algorithm][Template] 소수의 판별

1. 가장 기본적인 소수 판별 

   - 시간복잡도 : O(N)

#include <iostream>
#include <vector>

using namespace std;

int x;

bool isPrime(int x) {
    for (int i = 2; i < x; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

int main(void) {
    cin >> x;

    cout << isPrime(x) << endl;

    return 0 ;
}

2. 성능을 높인 소수 판별

   - 시간복잡도 : O(sqrt(N))

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int x;

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

int main(void) {
    cin >> x;

    cout << isPrime(x) << endl;

    return 0 ;
}

2. 에라토스테네스의 체(성능 업그레이드 버전)

   - 시간복잡도 : O(N*log(log(N)))

   - 다수의 소수를 구할 경우에 사용한다.

   - 동작 과정

      1) 2부터 N까지의 모든 자연수를 나열한다.

      2) 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.

      3) 남은 수 중에서 i의 배수를 모두 제거한다.(i를 제거하지는 않는다, N까지의 i의 배수 제거)

      4) 더 이상 반복할 수 없을 때까지 2), 3) 과정을 반복한다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int n = 1000;
vector<bool> prime(n+1, true);

// 에라토스테네스의 체
void makePrime(int n) {
    for (int i = 2; i <= sqrt(n); i++) {
        if (prime[i]) {
            int j = 2;
            while (i * j <= n) {
                prime[i * j] = false;
                j++;
            }
        }
    }
}

int main(void) {

    makePrime(n);

    // 0, 1 은 소수가 아니다.
    prime[0] = false;
    prime[1] = false;

    for (int i = 0; i <= n; i++) {
        if (prime[i])
            cout << i << " ";
    }
    cout << endl;

    return 0;
}

 

총정리 : 다수의 소수를 판별할 땐 3번[O(N*log(log(N)))]을, 적은 수의 소수를 판별할 땐 2번[O(sqrt(N))]을 사용하자.