[Algorithm] 소수 판별

들어가기 앞서,

• 소수는 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수이다.
• 간혹 코딩 테스트에선, 어떠한 자연수가 소수인지 아닌지 판별하거나,
• 1부터 N까지의 모든 소수를 출력해야 하는 문제 등이 출제된다.
• 따라서, 해당 포스팅에선 두 가지 문제를 해결하는 효율적인 방법에 대해서 다뤄볼 것이다.

특정 자연수의 소수 판별

• 특정한 자연수 X가 소수인지 아닌지 효율적으로 확인하기 위해선,

• 자연수 X의 제곱근까지 나누어떨어지는 수가 있는지 없는지 확인하면 된다.

• 해당 알고리즘의 시간 복잡도는, 자연수 X의 제곱근까지만 확인하므로 O(X^1/2)이다.

    import math
  
    # 소수 판별 함수
    def is_prime_number(x):
        # 2부터 x의 제곱근까지의 모든 수를 확인하며
        for i in range(2, int(math.sqrt(x)) + 1):
            # x가 해당 수로 나누어떨어진다면
            if (x % i == 0):
                return False # 소수가 아님
        return True # 소수임
  
    print(is_prime_number(4))
    print(is_prime_number(7))

2부터 N까지의 모든 소수 판별 (에라토스테네스의 체)

• 에라토스테네스의 체는, N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있으며, 알고리즘은 다음과 같다.
  1. 2부터 N까지의 모든 자연수를 나열한다.
  2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다. (i는 N의 제곱근까지만 증가시키며 확인한다.)
  3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.)
  4. 더 이상 반복할 수 없을 때까지 2번과 3번 과정을 반복한다.
• 에라토스테네스의 체 알고리즘의 시간 복잡도는 O(NloglogN) 이다.
• 하지만, N 만큼의 메모리가 필요하므로, N의 값이 크다면 사용하기 어렵다.

import math

# 2부터 1000까지의 모든 수에 대하여 소수 판별
n = 1000

# 처음엔 모든 수가 소수인 것으로 초기화
array = [True] * (n+1)

# 에라토스테네스의 체 알고리즘
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
    if (array[n] == True): # i가 소수인 경우
        # i를 제외한 i의 모든 배수를 False 처리
        j = 2
        while (i * j <= n):
            array[i*j] = False
            j += 1

# 모든 소수 출력
for i in range(2, n+1):
    if array[i] == True:
        print(i, end = ' ')

참고

• 이것이 취업을 위한 코딩테스트다. with python