에라토스테네스의 체

2부터 N까지의 소수를 찾는 알고리즘 중 구현하기도 쉽고 엄청 빠른 알고리즘

1. 2부터 시작해서 N까지를 일단 소수라고 해놓음
2. 2부터 시작해서 2는 소수이므로 그대로 놔두는데 2의 배수들을 소수가 아니라고 표시
3. 3으로 넘어가서 3은 소수이므로 그대로 놔두고 3의 배수들은 소수가 아니라고 표시
4. n의 제곱근까지의 수의 배수에 대해서 확인하면 됨.

def sieve_of_eratosthenes(n):
  """
  에라토스테네스의 체를 사용하여 n 이하의 모든 소수를 찾는 함수입니다.

  Args:
    n: 탐색 범위

  Returns:
    n 이하의 모든 소수를 담은 리스트
  """
  # 2부터 n까지의 모든 숫자를 True로 초기화합니다.
  primes = [True] * (n + 1)

  # 0과 1은 소수가 아니므로 False로 설정합니다.
  primes[0] = primes[1] = False

  # 2부터 제곱근 n까지 반복합니다.
  for i in range(2, int(n ** 0.5) + 1):
    # i가 소수라면
    if primes[i]:
      # i의 배수를 모두 False로 설정합니다.
      for j in range(i * i, n + 1, i):
        primes[j] = False

  # True인 인덱스를 리스트에 담아 반환합니다.
  return [i for i, p in enumerate(primes) if p]

# 예시
n = 100
primes = sieve_of_eratosthenes(n)
print(primes)

코드는 제미나이가 생성해줌.
주목할만한건 제곱근을 int(n ** 0.5)로 표현을 할 수 있었구나...