[수학] 소수판정 알고리즘

728x90

개요

백준 문제풀이과정에서 유용하게 사용했던 알고리즘들을 유형별로 정리하여 분석 및 복습하고자 별도의 글로 정리하게 됨

정의: 소수(Prime Number)

소수란 자신보다 작은 수들의 곱으로 만들어질 수 없는, 약수를 1과 자신밖에 가지지 못하는 수를 말합니다.

소수가 등장하는 순서에 규칙이 존재하지 않기 때문에, 소수를 판정하는 알고리즘은 시간복잡도가 중요합니다.

방법1. 약수범위 내에서 하나씩 나눠보며 소수여부 판단

1) 2부터 1씩 늘려가며 나눠보고 판단하기

1은 모든 소수의 약수이므로, 2부터 1씩 늘려가며 판별하고자 하는 숫자와 일일히 나눠보는 방법으로,

가장 간단하면서 원초적인 방법입니다.

// 판독하고자 하는 숫자: n
i값을 2부터 n까지 1씩 늘리며 순회하는 과정에서 아래 작업을 반복수행합니다:
    n과 i의 나머지연산 수행 결과가 0인지 확인하고,
    만약 0이면 소수가 아닌것으로 판단하고 작업을 종료합니다.

여기까지 코드가 종료되지 않고 오면 소수인것으로 판단합니다.

시간복잡도: O(n)
특이사항
- 가장 간단.
- 소수가 아닌경우 소수인 경우보다 빠르게 판단 가능
- 소수일 경우 연산시간이 굉장히 오래 걸림 (=최악의 경우)

2) 판단하고자 하는 숫자의 절반까지만 확인하기

판단하고자 하는 숫자가 나오기 전까지 모든 숫자를 확인하는 방법은 비효율적입니다.

사실 그중 절반은 확인할 필요가 없는 숫자이기 때문입니다.

가령 30이라는 숫자가 있다면, 30을 나눌 수 있는 숫자가 15이상에서는 나올 수 없습니다.

이유는 가장 작은 소수가 2이기 때문입니다.

2보다 작은 수는 1밖에 없는데, 1로 나눠진 숫자는 자기 자신일 것이므로, 연산해보는 의미가 없습니다.

// 판독하고자 하는 숫자: n
i값을 2부터 **n/2까지** 1씩 늘리며 순회하는 과정에서 아래 작업을 반복수행합니다:
    n과 i의 나머지연산 수행 결과가 0인지 확인하고,
    만약 0이면 소수가 아닌것으로 판단하고 작업을 종료합니다.

여기까지 코드가 종료되지 않고 오면 소수인것으로 판단합니다.

시간복잡도: O(n) (연산횟수는 n/2이나, 계수는 시간복잡도에서 무시)
특이사항
- 1번 방법보다 비교적 연산량을 줄일 수 있음
- 최악의 경우 연산시간이 굉장히 오래 걸린다는 단점은 바뀌지 않음

3) sqrt(판단할 숫자)만큼만 확인하기

사실 절반까지 확인하는 방법조차도 연산량을 더 줄일 수 있습니다.

판단할 숫자에 약수가 1과 자신을 제외하고 없으면 소수였습니다.

이말을 다른 관점으로 본다면, 약수를 구하는 과정을 간단하게하면 소수판단을 빠르게 할 수 있다는 뜻입니다.

가령 36의 약수를 구했다고 가정해보겠습니다.

36의 약수는 1, 2, 3, 6, 12, 24, 36입니다.

대부분의 경우 6이후에는 일일히 대입해보며 약수를 구하지 않으실 겁니다. 앞에서 구한 약수와 대칭을 이루기 때문입니다.

6은 처음에 약수를 찾고자 했던 36의 제곱근입니다. sqrt(36)의 결과값이죠.

다시 말해, 우리는 판단할 숫자의 제곱근까지만 확인해도 소수여부를 확인할 수 있습니다.

// 판독하고자 하는 숫자: n
i값을 2부터 **sqrt(n)보다 커지기 전까지** 1씩 늘리며 순회하는 과정에서 아래 작업을 반복수행합니다:
    n과 i의 나머지연산 수행 결과가 0인지 확인하고,
    만약 0이면 소수가 아닌것으로 판단하고 작업을 종료합니다.

여기까지 코드가 종료되지 않고 오면 소수인것으로 판단합니다.

시간복잡도: O(sqrt(n))
특이사항
- 1,2번 방법보다 비교적 연산량을 크게 줄일 수 있음

방법2. 이전 숫자의 소수판독결과를 저장하여 다음 숫자의 소수여부 판단

앞선 방법들은 특정 숫자의 소수여부를 단건으로 판단할 때 유용한 알고리즘들이었습니다.

하지만 만약 연속된 여러 수들의 소수판단이 필요한 상황이라면 중복된 연산과정들이 많아질 가능성이 있습니다.

이를 방지하기 위해 연산결과를 저장하여 소수판독 속도를 향상시킬 수 있습니다.

4) 소수표를 활용하여 판단하기 (에라토스테네스의 체)

에라토스테네스의 체란 고대 그리스 수학자 에라토스테네스가 만들어낸 방법으로, 체와 같이 사전에 이미 판단된 소수리스트를 활용하여 체처럼 소수를 걸러내는 방법입니다.

소수리스트를 만들어 사용하는 것의 장점은 판단할 숫자들의 범위를 알고 있을 때, 한번 판단한 소수결과를 저장하여 재사용하므로 중복연산횟수가 줄어듭니다.

// 판독하고자 하는 숫자: a1, a2, ..., an
가장_큰_숫자 = ak;
소수표=boolean형 배열(가장_큰_숫자+1); // 편의상 0번쨰 값을 사용하지 않을 것이기 때문
배열초기화(소수표, true) // boolean형 배열을 모두 true로 초기화
소수표[1] = false; // 1: 소수 아님
i를 2부터 "가장_큰_숫자"까지, 1씩 커지면서:
    만약 소수표[i]가 false이면:
        현순회 종료 & 다음순회로 이동 // = continue

    j를 2부터 시작하여, (i*j)가 "가장_큰_숫자"보다 작거나 같은 동안 1씩 커지면서:
        소수표[i*j] = false;

에라토스테네스의 체

위의 글을 참고하여 조금 더 생각해보면 시간복잡도가 조금 더 줄어듭니다.

1) 소수여부 변경 반복문의 시작범위 최적화

소수여부를 반복하기 위해 순회되는 내부반복문을 최적화 해보겠습니다.

위에 작성해둔 슈도코드를 보면, j를 항상 2부터 시작합니다.

하지만 여기에서 생각을 해보면, 만약 i가 7일 때 해당 반복문이 실행중이라면 이미 7*2는 i가 2일 때 연산이 되었을 겁니다.

따라서 해당 반복문에서 기존에 처리된 값을 다시 false로 바꾸는 작업을 할 필요가 없으므로, j가 i와 같아지는 7*7에서 시작되면 기존에 처리된 값을 다시 처리하는 일이 없어집니다.

2) 소수 탐색 반복문의 끝범위 최적화

이번엔 “i를 2부터 “가장큰숫자”까지 1씩 커지면서 순회”되는 외부반복문에 대하여 최적화 해보려고 합니다.

i가 1씩 커지면서 2부터 “가장큰숫자”까지 순회하도록 되어있는 코드는 위의 시작범위 최적화로 인해 i*i가 n보다 커지는 시점부터는 더이상의 내부반복문에서 진리값이 변경되지 않습니다.

따라서 조건문이 ‘“가장큰숫자”까지’였던 슈도코드는 ‘i*i가 “가장큰숫자”보다 작거나 같을 때 까지’로 바꾸는 것이 연산횟수를 줄일 수 있습니다.

1과 2를 통해 최적화된 에라토스테네스의 체의 슈도코드는 다음과 같습니다:

// 판독하고자 하는 숫자: a1, a2, ..., an
가장_큰_숫자 = ak;
소수표=boolean형 배열(가장_큰_숫자+1); // 편의상 0번쨰 값을 사용하지 않을 것이기 때문
배열초기화(소수표, true) // boolean형 배열을 모두 true로 초기화
소수표[1] = false; // 1: 소수 아님
i를 2부터 i*i가 "가장_큰_숫자"보다 작거나 같을 때 까지, 1씩 커지면서:
    만약 소수표[i]가 false이면:
        현순회 종료 & 다음순회로 이동 // = continue

    j를 i*i부터 시작하여, (i*j)가 "가장_큰_숫자"보다 작거나 같은 동안 1씩 커지면서:
        소수표[i*j] = false;

시간복잡도: O(nlog(logn)) (초기연산) | O(1) (향후사용)
특이사항
- 이전 연산결과를 저장하여 재사용 가능
- 초기 연산비용이 일부 소요되지만, 향후 사용 시 O(1)로 빠르게 접근 가능

5) 앞서 연산된 소수로만 나눠보고 판단하기(IDEA)

일일히 연산하는 것은 반복적인 과정을 발생시킵니다.

가령 4로 나눠지는 수는 2로도 나눠질 것이므로, 굳이 2번 연산시킬 필요가 없습니다.

4를 약수로 가지는 수가 2를 약수로 가지지 못하는 경우는 없기 때문입니다.

다시 말해, 임의의 소수로 나눠보았을 때 안나눠진다면, 굳이 그 배수로 다시 연산할 필요가 없습니다.

따라서 앞에 연산되었던 소수들을 저장해놓고, 해당 소수들로만 나눠보면 연산횟수를 줄일 수 있습니다.

이 방법은 실제 문제풀이를 하면서 써본적은 없어서, 향후 관련 문제가 나왔을 때 한번 더 정리해보도록 하겠습니다.