소수 (1) - 소수 판별하기

1. 알고리즘 개요

 

[그림] 소수 판별 알고리즘

 

소수 판별 알고리즘은 이름 그대로 정수를 입력받아서 해당 정수가 소수인지 아닌지 판별하는 알고리즘이다. 소수란 1과 자기자신 외에는 나누어 떨어지는 정수가 없는 양의 정수이다. 소수를 판별하는 방법은 매우 간단한데, 소수를 판별하려는 정수 N에 대하여 2 ~ N-1까지 나누어보고 모든 나머지가 0이 아니라면 그 수를 소수로 생각 할 수 있다. 

 

---

Prime Number Discrimination

 

(1) 정수 N을 입력받는다.

 

(2) 2 ~ N-1까지의 수로 N을 나누고 나머지를 확인한다.

 

(3) 모든 나머지가 0이 아니라면 그 수를 소수로 판별한다.

 

---

 

이러한 방식으로 구현하게 되면 알고리즘의 시간 복잡도는 $O(n)$이 된다. 그러나 굳이 N-1까지 모두 확인할 필요가 없다. 12를 예로 보자. 12의 약수들을 분석하기 위해 2 ~ N-1까지 나눴을 때 나누어 떨어지는 경우를 모두 확인해보자. 

 

---

 

$12 / 2 = 6$

$12 / 3 = 4$

$12 / 4 = 3$

$12 / 6 = 2$

 

---

 

12를 나누었을 때 나누어 떨어지는 2, 3, 4, 6의 경우 대칭구조를 확인할 수 있다. 2로 나눈 경우 6이 되고, 6으로 나눈 경우 2가 된다. 3으로 나누었을 때 4가 되고, 4로 나누었을 때 3이된다. 이는 같은 연산을 중복해서 수행하는 것으로 매우 비효율적이다. 합성수 $X$가 $N \times M$으로 합성되고, 두 약수의 관계가 $N \geq M$이라고 할 때, 반드시 $N \geq \sqrt{X}$ 이고, $M \leq \sqrt{X}$이다. 때문에, $\sqrt{X}$까지만 확인해봐도 그 전에 $M$이 약수로서 걸리게 되고, 소수 여부를 알 수 있게 된다.

 

2. 소스코드

#include <cstdio>
#include <cmath>


/**
 * 2 ~ N-1까지 확인
 * */
bool isPrime(int u) {
    for (int i = 2; i < u; i++) {
        if (u % i == 0)
            return false;
    }
    return true;
}

/**
 * 2 ~ sqrt(N)까지 확인
 * */
bool improved_isPrime(int u) {
    for (int i = 2; i <= sqrt(u); i++) {
        if (u % i == 0)
            return false;
    }
    return true;
}

int main() {
    bool a = isPrime(12);
    bool b = improved_isPrime(12);

    printf(a ? "T\n" : "F\n");
    printf(b ? "T\n" : "F\n");
    return 0;
}

 

gusdnd852/TIL

모든 소스코드는 Github에서 확인할 수 있습니다. 

 

3. Reference