[알고리즘] 소수 판별법 (Primality Test)

소수와 합성수

소수 (Prime Number)과 자기 자신으로만 나누어떨어지는 자연수를 뜻한다. 가령 자연수 로만 나누어떨어지므로 소수다. (참고로 는 소수중 유일한 짝수다.)

반면 합성수 (Composite Number) 이상의 자연수 중 나누어떨어지는 수(약수 또는 divisor)가 개 이상인 경우에 해당한다. 예를 들어 자연수 이상의 자연수 중 개의 수로 나누어떨어지므로 합성수다.

2, 3, 4, 6, 9, 12, 18, 36

끝으로 소수와 합성수에 전부 해당하지 않는 수가 있는데, 바로 자기 자신으로만 나누어떨어지는 수다. 자연수 이 그러하다.

약수 세기

자연수 의 약수(divisor)를 세보도록 하자. 가장 쉬운 방법은 에서 까지를 순회하며 과 나누어떨어지는지 하나하나 확인해보는 것이다. (시간복잡도: )

def n_divisors(n):
    i = 0
    result = 0
    while i <= n:
        if n % i == 0:
            result += 1
    return result

위의 방법보다 좀 더 효율적으로 약수를 세는 방법은 없을까? 바로 약수가 대칭성을 보인다는 특징을 활용하면 의 순회만으로도 약수를 세는 것이 가능하다. 다시 말하자면 자연수 의 약수일때 또한 의 약수가 되는 점을 이용하는 것이다. 을 예로 들어보겠다.

Step1. 과 곱해져 이 되는 수는 이다. 즉, 의 약수다.

Step2. 와 곱해져 이 되는 수는 이다. 즉, 의 약수다.

Step3. 과 곱해져 이 되는 수는 다. 즉, 의 약수다.

Step4. 와 곱해져 이 되는 수는 다. 즉, 의 약수다.

Step5. 에 나누어떨어지지 않는다. 즉, 의 약수가 아니다.

Step6. 은 제곱하여 이 된다. 즉, 의 약수다.

즉, 개의 약수를 갖는다. 단 번만의 순회로 의 모든 약수를 확인했다.

이 방법을 파이썬 코드로 구현해보면 아래와 같다. (시간복잡도: )

def n_divisors(n):
    i = 1
    result = 0
    while i * i < n:
        if n % i == 0:
            result += 2  # Count symmetric divisors
        i += 1
    if i * i == n:
        result += 1
    return result

소수 판별법

[2, n]의 범위에 약수가 존재하는지 확인함으로써 소수 판별법 (primality test)을 구현할 수 있다. (시간복잡도: )

def primality(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

1은 소수도 합성수도 아니므로 이 알고리즘은 를 만족하는 경우에만 동작한다.

연습문제: MinPerimeterRectangle

출처: Codility Lesson 10 - MinPerimeterRectangle

Task Description:

An integer N is given, representing the area of some rectangle.

The area of a rectangle whose sides are of length A and B is A * B, and the perimeter is 2 * (A + B).

The goal is to find the minimal perimeter of any rectangle whose area equals N. The sides of this rectangle should be only integers.

For example, given integer N = 30, rectangles of area 30 are:

  • (1, 30), with a perimeter of 62,
  • (2, 15), with a perimeter of 34,
  • (3, 10), with a perimeter of 26,
  • (5, 6), with a perimeter of 22.

Write a function:

def solution(N)

that, given an integer N, returns the minimal perimeter of any rectangle whose area is exactly equal to N.

For example, given an integer N = 30, the function should return 22, as explained above.

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..1,000,000,000].

Solution:

def solution(N):
    min_perimeter = 2 * (1 + N)
    i = 2
    while i ** 2 <= N:
        if N % i == 0:
            A, B = i, N // i
            min_perimeter = min(2*(A+B), min_perimeter)
        i += 1
    return min_perimeter

참고자료