Sieve of Eratosthenes

목차

• 소수(Prime Number)란?
• 소수 판별법(Prime Number Checking)
• 에라토스테네스의 채 (Sieve of Eratosthenes)
• ✏️ 연습 문제

---

소수(Prime Number)란?

1과 자기 자신 이외의 약수를 갖지 않는 2이상의 자연수 ex) 2. 3. 5. 7. 11. 13, ….

⚠️1은 소수가 아닙니다.

---

소수 판별법(Prime Number Checking)

주어진 수가 소수인지 어떻게 알 수 있을까요?

1. 전부 나누어 보기

2부터 N - 1로 나누어 떨어지는지 확인하는 방법입니다.

시간 복잡도는 O(N)입니다.

def is_prime(n):
    # 1은 소수가 아니므로 제외
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

# 테스트
print(is_prime(11))  # True
print(is_prime(15))  # False

2. 홀수로 나누어보기

수의 절반은 짝수입니다.

2를 제외한 모든 짝수는 소수가 아니므로 홀수로만 나누어 봅니다.

탐색 범위가 절반으로 줄어들어 시간 복잡도는 O(N / 2)입니다.

def is_prime(n):
    if n <= 1:
        return False
    # 2는 소수
    if n == 2:
        return True
    # 2가 아닌 짝수는 소수가 아니다.
    if n % 2 == 0:
        return False
    # 3부터 N - 1 까지의 홀수만 검사
    for i in range(3, n, 2):
        if n % i == 0:
            return False
    return True

💡소수를 더 빠르게 구할 수 없을까요?

3. 가장 큰 약수 생각해보기

소수는 1과 자기 자신 이외의 약수는 가지지 않습니다.

소수가 아닌 합성수는 약수를 가지며, 가장 큰 약수는 N의 제곱근 이하의 가장 큰 정수입니다.

따라서 N의 제곱근 이하의 정수들을 약수로 가지지 않는다면 소수임이 증명됩니다.

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    # 3부터 √n이하의 가장 큰 정수까지 홀수만 검사
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

---

에라토스테네스의 체(Sieve of Eratosthenes)

에라토스테네스의 체(Sieve of EratosThenes)는 고대 그리스의 수학자 에라토스테네스가 고안한 소수 판별법입니다.

원리

모든 합성수는 적어도 하나의 소수로 나누어 떨어짐은 자명합니다.

따라서 모든 소수의 배수를 제거하면 모든 합성수를 거를 수 있습니다.

N이하의 수에서 소수의 배수를 제거 후 남는 소수를 찾아보겠습니다.

def sieve_of_eratosthenes(n):
    # n보다 작거나 같은 모든 수의 소수 여부를 저장할 리스트(True: 소수, False: 소수가 아님)
    is_prime = [True] * (n + 1)
    is_prime[0:2] = [False, False]  # 0과 1은 소수가 아님
    
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n + 1, i):
                is_prime[j] = False
    # 소수 목록 반환
    primes = [i for i, prime in enumerate(is_prime) if prime]
    return primes

# 테스트
print(sieve_of_eratosthenes(50))
# 출력 예시: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

⌛시간복잡도

에라토스테네스의 채는 각 소수 $p$에 대해 $\frac{N}{p}$번의 연산이 필요하므로 시간복잡도는 다음과 같습니다.

따라서 전체 시간 복잡도는 O(NloglogN)가 됩니다.

---

✏️ 연습 문제

Silver IV : BOJ 02960, 에라토스테네스의 체

https://www.acmicpc.net/problem/2960

💡에라토스테네스의 체를 구현해 합성수를 지우는 횟수를 추적하면 됩니다.

Silver I : BOJ 01747, 소수&팰린드롬

https://www.acmicpc.net/problem/1747

💡N 이상의 소수 중 가장 작은 팰린드롬 수를 찾으면 됩니다. 우선, N이상의 소수부터 구해봅시다. 참고로 98,689 ≤ N ≤ 1,000,000이면, 정답은 1003001입니다.