소수판별 알고리즘 - 파이썬 (Python)

알고리즘 문제를 풀다보면 특정 수들이 소수인지 판단하도록 요구하는 문제들이 줄곧 있다.

 

아예 대놓고 소수찾기라는 문제만 쳐봐도 꽤 많은 문제들이 나올 것이다.

 

 

소수는 영어로 Prime Number라고 부르며 1과 자기자신 외에는 어떠한 수로도 나누어 떨어지지 않는 수를 말한다. 

 

특정 수 N이 소수인지 아닌지 구하는 법은 바로 이 특징을 활용하여 2부터 N-1 까지의 수로 해당 수를 나눠보고, 이 과정에서 어떠한 수에 의해 나누어 떨어지는지 확인하는 것이다.

 

나누어떨어지지 않는다면 해당 수는 소수인 것이고, 도중에 다른 수에 의해 나누어 떨어진다면 그 수는 소수가 아닐 것이다.

 

이를 코드로 표현하면 다음과 같다.

 

def is_prime_num(n):
    for i in range(2, n):
        if n % i == 0:
            return False # i로 나누어 떨어지면 소수가 아니므로 False 리턴
    
    return True # False가 리턴되지 않고 for문을 빠져나왔다면 소수이므로 True 리턴

 

위 방식은 입력값으로 받는 숫자 X에 대하여 2 ~ X-1번까지, 즉 X-2번의 연산이 필요하며 이는 시간복잡도 O(x)로 표현할 수 있겠다.

 

 

하지만 우리는 약수의 특성을 활용해서 이 연산 횟수를 반으로 줄여줄 수 있다. 

 

여기서 말하는 약수의 특성이란, 특정 수 N의 약수들을 일렬로 나열했을 때 그 중 가운데의 수를 중심으로 약수가 대칭된다는 것이다.

 

16을 예로 들어보자.

 

16의 약수들을 일렬로 나열하면 1, 2, 4, 8, 16이 된다.

 

중간값 4를 기준으로 양 옆을 보면 약수들이 서로 대칭되고 있음을 확인할 수 있다. (1 * 16 = 16 * 1, 2 * 8 = 8 * 2)

 

다시말해, 만약 우리가 16의 약수를 찾고 싶다면 16의 약수의 중간값을 기준으로 한 쪽만 검사를 하더라도 다른 쪽의 약수들을 알 수 있다.

 

여기서 중간값은 찾고자하는 수의 제곱근 값으로 가정해 처리할 수 있으며, 이 제곱근 값을 기준으로 왼쪽에 약수가 하나도 존재하지 않는다면 제곱근 값 기준 오른쪽에도 약수가 존재하지 않는다고 확신할 수 있다.

 

이를 통해 우리는 기존 for문이 2에서 N-1까지 돌았던 것을 2에서 N의 제곱근까지만 돌도록 처리해주어 연산 횟수를 절반에 가깝게 줄여줄 수 있다.

 

이 방식으로 접근했을 때 작성한 코드는 다음과 같다.

 

# 제곱근을 구하기 위해 math 라이브러리 임포트
import math

def is_prime_num(n):
    for i in range(2, int(math.sqrt(n))+1): # n의 제곱근을 정수화 시켜준 후 + 1
        if n % i == 0:
            return False

    return True

 

 

에라토스테네스의 체

 

우리는 위에서 특정 수 N이 주어졌을 때, 그 수가 소수인지 아닌지 판별하는 방법을 알아봤다.

 

그런데 만약 여러 개의 수에 대하여 소수 판별을 해줘야하는 상황이라면 어떨까?

 

예컨대 100 ~ 300 사이의 모든 소수들을 구해야하는 상황이라면 우리는 위의 방식을 이용해 하나하나 모든 수들을 판별해줘야할까?

 

계산에 소요되는 시간과 수고스러움을 생각해봤을 때 다른 방법이 필요해보인다.

 

그리고 이 상황에서 사용할 수 있는 알고리즘 중 하나가 에라토스테네스의 체 방식이다.

 

에라토스테네스의 체 알고리즘의 작동방식은 다음과 같다.

 

1. 2 ~ N까지의 범위가 담긴 배열을 만든다.

 

2. 해당 배열 내의 가장 작은 수 i 부터 시작하여, i의 배수들을 해당 배열에서 지워준다. (i는 소수이기 때문에 i자체는 지우지 않는다.)

 

3. 주어진 범위 내에서 i의 배수가 모두 지워지면 i 다음으로 작은 수의 배수를 같은 방식으로 배열에서 지워준다.

 

4. 더 이상 반복할 수 없을 때까지 2, 3번의 과정을 반복해준다.

 

 

에라토스테네스의 체 방식을 코드로 구현하면 다음과 같다.

 

def is_prime_num(n):
    arr = [True] * (n + 1) # 특정 수가 지워졌는지 아닌지 확인하기 위한 배열
    arr[0] = False
    arr[1] = False

    for i in range(2, n + 1):
        if arr[i] == True: # 특정 수가 지워지지 않았다면 (소수여서)
            j = 2

            while (i * j) <= n:
                arr[i*j] = False # i의 배수의 값을 False로 지워준다.
                j += 1

    return arr

arr = is_prime_num(50) # 0 ~ 50중 소수를 구하기 위한 함수

for i in range(len(arr)):
    if arr[i] == True:
        print(i, end=' ')

 

이 방식의 알고리즘은 거의 상수시간과 가까울 정도로 빠른 시간 내에 연산을 가능하게 해준다.

 

또한, 앞서 말한 약수의 특징을 이용해서 반복문의 횟수를 줄여주는 것이 가능하다.

 

즉, 범위 2 ~ N에서 N의 제곱근값보다 작은 부분들에 대한 처리가 끝나면, 제곱근값보다 큰 부분의 값 또한 처리가 된다는 말이다.

 

 

따라서 이를 코드로 작성하면 다음과 같다.

 

import math

def is_prime_num(n):
    arr = [True] * (n + 1)
    arr[0] = False
    arr[1] = False

    for i in range(2, int(math.sqrt(n)+1)):
        if arr[i] == True:
            j = 2

            while (i * j) <= n:
                arr[i*j] = False
                j += 1

    return arr

arr = is_prime_num(50)

for i in range(len(arr)):
    if arr[i] == True:
        print(i, end=' ')

 

 

소수판별 관련 문제

 

[백준] 1929번 소수 구하기 - seongonion.tistory.com/44

[백준] 1929번 소수 구하기 - 파이썬(Python)

[백준] 4948번 베르트랑 공준 - seongonion.tistory.com/45

[백준] 4948번 베르트랑 공준 - 파이썬(Python)