[알고리즘] 소수(Prime number) 판별하기

오늘도 알고리즘 공부를 하면서 중학교 수학을 다시 한 번 상기한다. 그때 이런 수학적 개념이 이렇게 활용된다는 것을 알았으면 더 열심히 공부했을텐데 하는 아쉬움(+이과갈걸...)도 남는다.

• 소수(Prime Number)란?

  • 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 의미한다. 반대로, 소수의 합으로 나타낼 수 있는 수는 '합성수(composite)'라고 한다.

  • 소수와 합성수를 구분하는 명확한 공식은 아직 밝혀지지 않았다. 이 때문에 소수를 구하기 위해서 알고리즘이 필요하다.

• 소수 판별 알고리즘

  • [방법 1] 주어진 수가 소수인지 알기 위해서는 주어진 수를 그 수보다 작은 모든 수로 나눠보면 된다. 그 결과 나머지가 0인 수가 1과 주어진 수 자신밖에 없다면 그 수는 소수이다.

    해당 알고리즘은 아래와 같이 표현할 수 있다.

    이 알고리즘의 시간복잡도는 O(n)이며, 문제점은 수가 매우 크거나 무수히 많은 수를 대상으로 소수를 판별할 때 상당히 많은 시간이 걸릴 수 있다는 것이다.

    def is_primenum(x):
     if x == 1:
         return False
     else:
         for denom in range(2, x):
             if x % denom == 0:
                 return False
         return True

  • [방법 2] 약수의 개념을 활용하여 소수를 조금 더 효율적으로 구하는 방법이다.
    16이 소수인지 판별하는 상황을 가정하자.

    [방법 1]을 적용하면 16을 2부터 16까지 나눠가면서 나누어 떨어지는지 확인할 것이다.

    16을 2부터 16까지 나누어 떨어지는 수는 [2, 4, 8, 16]이며 16은 소수가 아니다.
    그런데 나누어 떨어지는 수를 자세히 보면 [8, 16]은 [2, 4]에 4를 곱한 값이다.
    한편 16은 $4^2$와 동일하다.

    사례를 25로 바꾸어서 한번 더 살펴보자.
    25를 2부터 25까지 나누어 떨어지는 수는 [5, 25]이므로 25는 소수가 아니다.
    그런데 나누어 떨어지는 수를 자세히 보면 [25]는 [5]에 5를 곱한 값이다.
    한편 25는 $5^2$와 동일하다.

    이제 규칙이 보인다.

    소수 판별 시 나누어 떨어지는 수 뒤의 절반은 앞의 절반에 주어진 수의 제곱근을 곱한 값이다.
    따라서 앞의 절반을 구하면 뒤의 절반은 굳이 루프를 돌려서 구할 필요가 없다.

    즉, 소수 판별은 주어진 수 제곱근의 정수부분 + 1까지의 수를 통해서만 확인하면 된다.

    위 알고리즘을 수정해서 표현하면 아래와 같다.

     def is_primenum(x):
      if x == 1:
          return False
      else:
          for denom in range(2, int(x**0.5) + 1):
              if x % denom == 0:
                  return False
          return True

    해당 알고리즘의 시간복잡도는 O(n^0.5)로 줄어들었다.
    만약 소수 판별해야하는 수의 갯수가 10억개이고 수의 자릿수가 10억(또는 그 이상)이라면
    [방법 1]은 10억 x (10억 - 2) = 999,999,998,000,000,000번의 연산을 수행해야하는 반면
    [방법 2]는 10억 x (10억^0.5 + 1 - 1) = 31,622,776,601,684번으로 연산이 무려 99.99684%가 줄어드는 효과가 생기게 된다.