파이썬(Python) 1부터 10000 사이 소수 구하는 알고리즘 - 에라토스테네스의 체, 장점과 단점 | 유찬맨

소수를 구하는 알고리즘으로는 에라토스테네스의 체라는 것이 있습니다.

이 알고리즘은 1부터 주어진 범위까지의 숫자들 중 소수를 구하는데 사용됩니다.

 

아래 코드는 1부터 10000 사이의 소수를 구하는 코드입니다.

def get_primes(n):
    primes = [True] * (n+1) # 소수로 가정
    primes[0] = primes[1] = False # 0, 1은 소수가 아님
    for i in range(2, int(n**0.5)+1):
        if primes[i]: # 소수인 경우
            for j in range(i*i, n+1, i): # 그의 배수들은 소수가 아님
                primes[j] = False
    return [x for x in range(n+1) if primes[x]]

print(get_primes(10000))

위 코드는 get_primes 함수를 정의하고 n만큼의 소수를 구하는 함수이다.

primes 리스트는 True로 초기화 되어 있고, 0과 1은 소수가 아니므로 False로 초기화 해준다.

이후 for문으로 2부터 n의 제곱근까지 검사하며, 해당 숫자가 소수일 경우 그 숫자의 배수들은 소수가 아니므로 False로 변경해준다.

검사가 끝난 후에는 primes 리스트에서 True인 값들을 가진 인덱스들을 뽑아내서 반환합니다. 즉, 1부터 n까지의 소수들을 반환합니다. 위 코드는 n을 10000으로 설정하여 1부터 10000 사이의 소수를 구하는 코드입니다.

위 코드는 에라토스테네스의 체 알고리즘으로 구현하였고, 이 알고리즘은 효율적인 알고리즘 중 하나로 알려져 있다. 다른 알고리즘들도 있지만, 이 알고리즘은 구현이 간단하고 속도도 좋기 때문에 일반적으로 사용되는 것이다.

 

장점

1. 구현이 간단해서 이해하기 쉽다.
2. 속도가 빠르다.
3. 메모리 사용량이 적다.

단점

1. 일부 소수만 구할 수 있다. (1부터 n까지의 소수만 구할 수 있다.)
2. 소수를 구할 때 제곱근(sqrt(n))만큼의 시간이 걸린다.

에라토스테네스의 체는 일반적으로 소수 개수가 많을 때 효율적인 알고리즘 중 하나입니다. 그러나, 입력으로 받은 숫자 n이 매우 크다면 제곱근(sqrt(n))만큼의 시간이 걸릴 수 있어 속도가 느려질 수 있습니다.