소수(Prime Number) 판별 알고리즘: 에라토스테네스의 체

1. 단일 숫자 소수 판별 ($O(\sqrt{N})$)

어떤 수 $N$ 하나가 주어졌을 때, 이 수가 소수인지 확인하는 가장 정석적인 방법입니다. 2부터 $N-1$까지 전부 나눠볼 필요 없이, $N$의 제곱근($\sqrt{N}$)까지만 나눠봐도 충분합니다. 약수는 항상 대칭을 이루기 때문에 제곱근까지만 확인해도 시간 복잡도를 $O(\sqrt{N})$으로 대폭 줄일 수 있습니다.

pythonimport math

def is_prime(n):
    # 0과 1은 소수가 아님
    if n < 2:
        return False
        
    # 2부터 n의 제곱근까지만 확인
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False  # 나누어 떨어지면 소수가 아님
            
    return True # 모두 통과하면 소수

2. 특정 범위 안의 모든 소수 찾기 ($O(N \log \log N)$)

"1부터 100만까지의 소수를 모두 구하라"와 같이 다수의 소수를 한 번에 찾아야 할 때는 에라토스테네스의 체(Sieve of Eratosthenes) 를 무조건 사용해야 시간 초과를 피할 수 있습니다. 마치 체로 걸러내듯, 소수를 하나 찾으면 그 소수의 배수들을 모두 지워나가는 아주 빠르고 효율적인 방식입니다.

pythonimport math

def sieve_of_eratosthenes(n):
    # 처음엔 0, 1을 제외한 모든 수를 소수(True)로 간주
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    
    # n의 제곱근까지만 배수들을 지워주면 됨
    for i in range(2, int(math.sqrt(n)) + 1):
        if is_prime[i]: # i가 소수라면
            # i의 배수들을 모두 False(소수가 아님)로 처리
            # (i*2 대신 i*i부터 시작해도 무방함)
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
                
    # True로 남아있는 인덱스(숫자)만 리스트로 뽑아냄
    return [i for i in range(2, n + 1) if is_prime[i]]

 # 사용 예시: 50까지의 소수 구하기
primes = sieve_of_eratosthenes(50)
print(primes)

요약 비교 테이블