소수 스페셜 - 에라토스테네스의 체

알고리즘 문제에는 소수와 관련된 문제가 많이 등장한다. 무지 짜증난다.

 

해당 숫자가 소수인지 알수있는 알고리즘은 여러가지가 있는데

 

소수 여부를 알고싶은 숫자 N에 대해,

1) 직접 모든 수를 집어넣어 N의 약수가 1만 존재하는지 확인하는 방법과

2) 에라토스테네스의 체 방법이 대표적이다.

 

1번 방법은 어떻게 구현하느냐에 따라 시간복잡도가 길어지거나 짧아질 수 있는데, 

N의 약수인지 확인할 숫자의 범위를 지정해주면 조금은 빠르게 수행할 수 있겠다.

 

def is_prime(n):
    if n <= 1: # 1보다 작으면 소수가 아님
        return False
    if n <= 3: # 2와 3은 소수임
        return True
    if n % 2 == 0 or n % 3 == 0: # 2와 3의 배수를 확인 -> 소수가 아님
        return False 
        
    # 위 3개 조건에서 걸러지지 않으면, (25 이상의 2, 3 배수가 아닌 수들)
    i = 5 
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    # 6의 배수(소수 2와 3의 최소공배수) 주변숫자를 검사하면 좀더 효율적으로 갈 수 있음.
    # 기본적으로 처음 3개의 조건에 걸리지 않으면 시행하는것.
    return True

 

사실 소수의 검증을 스스로 해내기는 쉽지 않다. 이러저러하게 조건을 짜 볼수 있겠지만 큰 수에서도 확실하게 소수를 확인할 수 있는 방법은 아주 꼼꼼해야 하겠다.

 

그래서 나온것이 에라토스테네스의 체 이다.

 

말 그대로 체에 숫자들을 거르듯이 확인을 하는 것인데,

 

소수는 1과 자기자신 말고는 약수가 존재하면 안되기때문에 가상의 숫자 판을 만들어놓고

2부터 그 배수들을 하나씩 지워나가는 것이다. (2, 4, 6, 8 ...)

3, 4, 5, 6 계속해서 숫자들을 지워나가면, 지워지지 않은 수가 바로 소수가 된다.

 

위키피디아에 좋은 그림이 있어서 가져왔다. 설명이 모호할 수 있지만 그림을 보면 이해가 쉽다

 

그렇다면 이것을 어떻게 코드로 구현할 것인가?

 

정확히는 초기화된 리스트에서 소수를 선택하고, 그 배수를 전부 제거하는 형식이다.

 

먼저 2부터 시작하는 리스트를 생성한다. (30까지의 숫자로 설정)

 

is_prime = [True] * 31

is_prime[0] = is_prime[1] = False # 0과 1은 소수가 아님

 

첫번째 소수 2를 선택하고 배수를 전부 제거한다.

 

p = 2
for i in range(p * p, 31, p): # 2 * 2 부터 설정한 최대 수 까지, 2씩 증가 -> 2의 배수
    is_prime[i] = False

 

같은방법으로 다음 소수를 찾고 소수의 배수를 제거한다 

 

def sieve(n):
    is_prime = [True] * (n + 1)  # n까지 모든 수를 소수로 가정
    is_prime[0] = is_prime[1] = False  # 0과 1은 소수가 아님

    p = 2
    while (p * p <= n):
        if is_prime[p]:
            # p의 배수들을 False로 설정
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
        p += 1

    # 소수 리스트 반환
    prime_numbers = [p for p in range(n + 1) if is_prime[p]]
    return prime_numbers

# 사용 예제
n = 50  # 원하는 범위
prime_numbers = sieve(n)
print(prime_numbers)

 

이렇게 계속해서 p를 변경하며 소수들만 리스트로 반환하면 된다.

N이하의 소수들을 전부 찾으려면 N의 제곱근 까지 검사하면 되겠다. - while문 조건

 

실제로 맨 처음에 설명한 나누어지는 수를 찾는 소수 판별법과

에라토스테네스의 체의 시간 차이는 꽤나 나는 편이다.

 

import time

# is_prime 함수 정의
def is_prime(n):
    if n <= 1: 
        return False
    if n <= 3: 
        return True
    if n % 2 == 0 or n % 3 == 0: 
        return False 
    i = 5 
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

# sieve 함수 정의
def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while (p * p <= n):
        if is_prime[p]:
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
        p += 1
    prime_numbers = [p for p in range(n + 1) if is_prime[p]]
    return prime_numbers

# 시간 측정 및 성능 비교
n = 1000000  # 100만까지의 범위 내 소수 찾기

# is_prime 함수 시간 측정
start_time = time.time()
is_prime_results = [is_prime(i) for i in range(2, n + 1)]
end_time = time.time()
is_prime_time = end_time - start_time
print(f"is_prime function took {is_prime_time:.2f} seconds")

# sieve 함수 시간 측정
start_time = time.time()
sieve_results = sieve(n)
end_time = time.time()
sieve_time = end_time - start_time
print(f"sieve function took {sieve_time:.2f} seconds")

 

 

100만 까지의 범위에서 시행했을시, 

is_prime function took 1.70 seconds
sieve function took 0.13 seconds

 

10배 이상의 차이가 나는 것을 알 수 있다.

 

결론

어찌되었든 알고리즘 문제에는 소수에 대한 내용이 자주 등장한다.

 

소수를 찾을 수 있는 방법은 다양하고, 어떤것을 사용할 지는 머리에 떠오르는 것이 무엇인지가 중요하겠지.

 

에라토스테네스의 체는 생각보다 구현하기가 간단하다. 처음 볼때는 몰랐는데 직접 작성하고 살펴보니 이해가 된다.

 

잘 알아두고 잘 써먹어보자.