[Algorithms] 소수 찾기

소수 판별

Brute Force

def is_prime_number(n):
    if n == 1:
        return False

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

위 함수의 시간 복잡도는 $O(n)$이다.

약수의 특성을 이용하기

자연수 $n$이 $a \times b$로 표현될 때, $a \ge \sqrt n$이면 $b \le \sqrt n$ 이다.

위 특성을 이용하면 $\sqrt n$까지만 검증을 하도록 최적화 할 수 있다.

import math


def is_prime_number(n):
    if n == 1:
        return False

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

위 함수의 시간 복잡도는 $O(\sqrt n)$이다.

주어진 범위 이하의 모든 소수 찾기

Brute Force

def find_prime_list_under_number(n):
    prime_list = []

    if n == 1:
        return prime_list

    for i in range(2, n + 1):
        for j in range(2, i):
            if i % j == 0:
                break
        else:
            prime_list.append(i)
    return prime_list

위 함수의 시간 복잡도는 $O(n^2)$이다.

느리다.

약수의 특성을 이용하기

def find_prime_list_under_number(n):
    prime_list = []

    if n == 1:
        return prime_list

    for i in range(2, n + 1):
        for j in range(2, int(math.sqrt(i)) + 1):
            if i % j == 0:
                break
        else:
            prime_list.append(i)
    return prime_list

위 함수의 시간 복잡도는 $O(n^{3\over2})$이다.

여전히 느리다.

Sieve of Eratosthenes

에라토스테네스의 체를 사용하여 성능을 향상시켜보자.

def find_prime_list_under_number(n):
    sieve = [False, False] + [True] * (n - 1)

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

위 함수의 시간 복잡도는 $O(n\log(\log n))$이다.

선형 시간과 비슷한 시간 복잡도를 가진다.