[알고리즘] 간단한 소수 판별 알고리즘 (Swift)

소수

소수(Prime Number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 입니다.

간단한 소수 판별 알고리즘

그렇다면 해당 수가 소수인지 아닌지 어떻게 판별할까요?

아주 간단한 방식으로 소수인지 판별할 수 있습니다.
단순히 2부터 자기 자신의 수 - 1 까지의 수 중에서 나누었을 때, 나머지가 0이 되는 수가 하나라도 존재하면 소수가 아닙니다.

이 방식의 경우 시간 복잡도는 $O(n)$이 될 것입니다.

시간 복잡도를 줄일 수 있는 방법이 있을까요??

개선된 소수 판별 알고리즘

X를 2로 나누었을 때, 나머지가 0이라면 2는 X의 약수입니다.
그렇다면 X는 절대로 소수가 될 수 없겠죠?

X를 2로 나누었을 때, 몫 도 X의 약수 입니다.

이러한 성질을 이용해서 시간 복잡도를 줄일 수 있습니다.

예를 들어, 20의 약수는 [1, 2, 4, 5, 10, 20] 입니다.
이것은

• 1 X 20
• 2 X 10
• 4 X 5
• 5 X 4
• 10 X 2
• 20 X 1

대칭이 되는 것을 확인할 수 있습니다.
따라서 20이 소수인지 아닌지 판별할 때, 2부터 4까지에 대해서만 나누어서 나머지가 0인지 확인하면 되겠죠??
즉, 자기 자신의 제곱근 까지만 확인하면 됩니다.

개선된 소수 판별 알고리즘의 시간 복잡도는 $O(\sqrt{n})$ 이 될 것 입니다.

시간 복잡도 측면에서 엄청나게 빨라진 것을 확인하실 수 있겠죠?

다음 포스팅에서는 소수를 판별하는 알고리즘 중 하나인 에라토스테네스의 체 알고리즘에 대해 알아봅시다.