숫자 N이 주어졌을때 1부터 N까지의 소수를 모두 구하는 함수를 작성해보겠습니다.

단순하게 생각해보기

단순하게 모든 숫자를 순회하며 1을 제외한 수로 나눠지는지 ( 소수는 1와 자신을 제외한 수로 나누어지지 않는 수이므로) 확인하는 방법.

다만 모든 수를 다 나눠볼 필요는 없고, 자신의 절반 값까지만 확인해보면된다.

왜냐하면 자신의 절반 보다 큰 수는 x2를 하면 자신보다 큰 값이 나오기 때문이다. 
( 예) 10/2 = 5,  5×2 = 10 이지만 6×2=12 )

def get_prime_nums1(n):
    prime_nums = []

    for i in range(2, n + 1):
        flag = 1
        for j in range(2, i // 2 + 1):
            if i % j == 0:
                flag = 0
                break

        if flag == 1:
            prime_nums.append(i)

    return prime_nums
    
    
if __name__ == '__main__':

	print(get_prime_nums1(10)) # [2, 3, 5, 7]

최적화 하기

단순하게 순회하면 자신보다 작은 수로 나눠보는 방법은 단순한만큼 숫자의 범위가 커질수록 느립니다. 

그래서 좀 더 빠르게 구하기 위해 최적화를 해보겠습니다.

def get_prime_nums2(n):
    sieve = [True] * (n+1)

    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i]:
            for j in range(i + i, n+1, i):
                sieve[j] = False

    return [i for i in range(2, (n+1)) if sieve[i]]

if __name__ == '__main__':

	print(get_prime_nums2(10)) # [2, 3, 5, 7]

해당 함수는 에라토스테네스의 체를 구현한 함수인데요.
( 해당 원글의 python 코드는 n 값이 5, 6인 경우에 처리가 정상적으로 안되는 문제가 있어서 일부 코드를 수정했습니다. )

에라토스테네스의 체의 알고리즘은 아래와 같습니다.

2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 

– 자기 자신을 제외한 2의 배수를 모두 지운다.
– 남아있는 수 가운데 3은 소수이므로 자기 자신을 제외한 3의 배수를 모두 지운다.
– 남아있는 수 가운데 5는 소수이므로 자기 자신을 제외한 5의 배수를 모두 지운다.
– 남아있는 수 가운데 7은 소수이므로 자기 자신을 제외한 7의 배수를 모두 지운다.

위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

우선 함수를 실행하면 인자로 받은 숫자범위만큼 True로 정의한 리스트를 생성합니다.
( 이 리스트의 True False 를 토대로 소수여부를 판단합니다. True => 소수 )

그리고 2부터 n의 제곱근까지 루프를 돌면서 각 수의 배수를 False로 변경해줍니다.

모든 루프가 종료 된 후 True 인 요소들의 index를 리스트로 만들어서 리턴하여 소수의 리스트를 반환합니다.

속도 비교

import time


def get_prime_nums1(n):
    prime_nums = []

    for i in range(2, n + 1):
        flag = 1
        for j in range(2, i // 2 + 1):
            if i % j == 0:
                flag = 0
                break

        if flag == 1:
            prime_nums.append(i)

    return prime_nums


def get_prime_nums2(n):
    sieve = [True] * (n+1)

    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i]:
            for j in range(i + i, n+1, i):
                sieve[j] = False

    return [i for i in range(2, (n+1)) if sieve[i]]


if __name__ == '__main__':

    start = time.time()
    get_prime_nums1(10000)
    print("get_prime_nums1:", time.time() - start)

    start = time.time()
    get_prime_nums2(10000)
    print("get_prime_nums2:", time.time() - start
    

# get_prime_nums1: 0.22524499893188477
# get_prime_nums2: 0.0014650821685791016

이상으로 소수를 구하는 방법에 대해 알아보았습니다.

감사합니다. 😄