2. 소수 판별

소수 판별

수학 관련된 문제를 풀다보면 어떤 숫자가 소수인지 아닌지를 판별해야 할 때가 많다.
어떻게 어떤 수가 소수인지 아닌지 알 수 있을까?

소수

우선 소수란 자기 자신과 1로만 나누어 떨어지는 수이다.
이 때 1은 제외한다.

2, 3, 5, 7...

숫자 1개가 주어졌을 때 소수인지 판별하는 방법부터 보자.

시간 복잡도 O(N)

가장 간단하고, 생각하기 쉬운 아이디어이다.
주어진 수를 N이라고 했을 때 2~N-1로 나눠보며 나누어 떨어지지 않으면 소수이다.

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;  // 나누어 떨어지면 소수가 아님
    }
    return true;
}

int main() {
    int num;
    cout << "숫자를 입력하세요: ";
    cin >> num;

    if (isPrime(num)) {
        cout << num << "은 소수입니다." << endl;
    } else {
        cout << num << "은 소수가 아닙니다." << endl;
    }

    return 0;
}

시간 복잡도 O(root(N))

위의 아이디어에서 꼭 2~N-1로 다 나눠봐야 하는지에 초점을 맞춰서 좀 더 개선시켜보자.
어떤 수가 나눠진다면 나눈 수와 나눠진 값의 쌍을 가지게 된다.
예를 들어 24는 (2,12), (3,8), (4,6)의 쌍을 가진다.

이 때 쌍의 왼쪽에 있는 값은 root(N)보다 작거나 같은 값을 가지게 된다.
그러므로 2~N-1이 아닌 2~root(N)까지만 나눠봐도 소수 판별이 가능해진다.

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;  // 나누어 떨어지면 소수가 아님
    }
    return true;
}

int main() {
    int num;
    cout << "숫자를 입력하세요: ";
    cin >> num;

    if (isPrime(num)) {
        cout << num << "은 소수입니다." << endl;
    } else {
        cout << num << "은 소수가 아닙니다." << endl;
    }

    return 0;
}

에라토스테네스의 체

이번에는 숫자 1개 N에 대한 판별이 아닌 2~N까지 숫자 범위에서 판별하는 방법을 보자.
중학교였나 고등학교 수학 교과서에서 배웠던 기억이 있다.

아이디어는 소수의 배수는 소수가 아니라는 것에서 시작된다.
시작 지점인 2는 소수이고, 그러면 2의 배수는 소수가 아니다.
3은 소수이고, 3의 배수는 소수가 아니다.

반복문을 돌며 이렇게 소수의 배수에 체크를 하고, 체크가 되지 않은 수는 소수이다.
소수를 발견하면 그 소수에 대해 배수에 체크를 하며 범위에 대해 소수를 판별할 수 있다.

#include <iostream>
#include <vector>
using namespace std;

void sieveOfEratosthenes(int limit) {
    vector<bool> isPrime(limit + 1, true);
    isPrime[0] = isPrime[1] = false;  // 0과 1은 소수가 아님

    for (int i = 2; i * i <= limit; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= limit; j += i) {
                isPrime[j] = false;  // i의 배수는 소수가 아님
            }
        }
    }

    cout << "소수 목록: ";
    for (int i = 2; i <= limit; i++) {
        if (isPrime[i]) {
            cout << i << " ";
        }
    }
    cout << endl;
}

int main() {
    int limit;
    cout << "소수를 구할 범위를 입력하세요: ";
    cin >> limit;

    sieveOfEratosthenes(limit);

    return 0;
}

이 에라토스테네스의 체 알고리즘의 시간복잡도는 N*log(logN)으로 거의 선형과 같다.
다만 N만큼의 bool 배열이 필요하기 때문에 아주 큰 숫자에서는 메모리에 대해 주의해야 한다.
유용하게 사용할 곳이 많은 소수 판별 알고리즘이다.

---

https://www.acmicpc.net/problem/13926
이 문제는 1e18의 크기의 숫자에 대한 소수 판별과 소인수 분해가 필요하다.
숫자가 너무 크기에 위의 방법에는 한계가 있다.
그렇기에 이 문제를 풀려면 밀러-라빈 판별법, 폴라드로 알고리즘에 대해 공부를 해야한다.