에라토스테네스의 체

에라토스테네스의 체

임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는, 가장 간단하고 빠른 방법

1. 소수도 합성수도 아닌 1 제거
2. 남은 가장 작은 수는 소수
3. 해당 수의 배수를 제거
4. 2번 알고리즘으로 되돌아가기

라는 알고리즘으로, 초등학생 때 다들 한번씩 해봤던 기억이 있을 것이다..
이 에라토스테네스의 체 알고리즘으로 소수를 구하는 여러 알고리즘을 구현할 수 있다.

---

주어진 수보다 작은 소수들을 찾는 알고리즘

def eratosthenes_sieve(n):
    sieve = [True] * (n+1) # 모든 수를 소수로 가정하고 시작
    sieve[0] = sieve[1] = False # 0과 1은 소수가 아님

    for i in range(2, int(n**0.5)+1): # n의 제곱근까지만 확인하면 됨
        if sieve[i]: # i가 소수인 경우
            for j in range(i+i, n+1, i): # i의 배수를 모두 False로 설정
                sieve[j] = False

    return [i for i, is_prime in enumerate(sieve) if is_prime] # 소수인 인덱스만 반환

시간복잡도: O(n log(logn))

❗️ 참고

• enumerate(sieve) 함수는 리스트에서 원소와 그 원소의 인덱스를 함께 제공한다
• i, is_prime 는 sieve 리스트의 인덱스와 값을 할당받고 있다
• 따라서, 그 값(is_prime)이 True일 때만 그 인덱스 값(i)를 리스트에 넣는다

---

주어진 수가 소수임을 판별하는 알고리즘

def is_prime(n):
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False

    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6

    return True

코드 설명은 여기 참고
시간복잡도: O(√n)
주어진 수가 소수임을 판별하는 알고리즘만 필요하다면 이 코드만 쓰는 것이 좋다.