[Algorithm] 소수 판별 & 소수 리스트 만들기

소수(Prime Number)란?

1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수

 

소수를 판별하는 데는 2가지 방법이 있다.

 

1. 특정 수 N이 소수인지 알기위해, 2부터 N-1까지의 수로 N을 나눠보고, 어떤 수로도 나눠 떨어지지 않는 다면 N은 소수.
2. 에라토스테네스의 체를 이용하는 방법

1. 2부터 n-1까지의 수로 n을 나눠보기

첫번째 방법을 코드로 나타내면 다음과 같다.

def isPrime(n):
    for i in range(2, n):
        if n % i == 0:
            return False  
    return True

이 코드는 2부터 n-1까지 모든 숫자를 확인하며 소수인지 판별하는 방법이기 때문에 시간 복잡도가 O(n)이 나온다. 숫자가 커질수록 오래걸린다.

 

여기서 약수의 특성인 대칭성을 사용하면 연산 횟수를 줄일 수 있다.

대칭성이란, 특정 수 n의 약수들을 나열했을 때, 중간값을 기준으로 약수가 대칭이 된다는 특성이다.  이를 이용하면 중간값, 즉 n의 제곱근으로 처리할 수 있는 값을 중심으로 n의 제곱근보다 작은 수들에 약수가 없으면 큰 수에도 약수가 없는 것을 의미하고, 이는 n-1까지 확인할 필요 없이 2부터 n의 제곱근까지 확인해주면 된다는 뜻이다.

이 방식을 이용하면 시간 복잡도는 O(nlogn)이 된다. 

위의 이론을 바탕으로 다시 코드로 나타내면 아래와 같다.

def isPrime1(n):
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False  
    return True

# math 라이브러리를 import해서 사용해도 됨. 위와 같은 코드
import math

def isPrime2(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False  
    return True

2. 에라토스테네스의 체

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

 

1. 2부터 n-1까지의 배열을 만든다.
2. 배열을 하나씩 돌아가면서 가장 작은 숫자인 2부터 시작해 2는 먼저 소수 리스트에 넣어주고 그 배열내의 2의 배수들을 다 없애준다. (배수로 삭제된 수는 소수가 아님을 의미하니 확인하지 않는다.)
3. 배열이 끝 때까지 2번을 반복한다.

위의 작동방식을 이용해 소수 리스트를 만드는 코드는 다음과 같다.

n = int(input())
arr = [False, False] + [True] * (n - 1)
prime_num = []

for i in range(2, n + 1):
    if arr[i]:
        prime_num.append(i)
        # 소수 i의 배수를 다 False로 바꾸기
        for j in range(2*i, n + 1, i):
            arr[j] = False

에라토스테네스의 체는 1번 방법에 비해 매우 빠른 시간 내로 연산이 가능하게 해주고, n이 클 때 유리한 방법으로 불필요한 연산을 줄여준다.