[파이썬 코딩 도장] 40.6 심사문제: 소수 제너레이터 만들기

정답

일반적인 방법 모든 수에 대한 소수 여부를 확인

def prime_number_generator(start, stop):
  for n in range(start, stop):
    # 소수여부 확인용 변수 생성
    is_prime = True
    # start 부터 stop의 모든 수에 대해 소수여부 확인
    for i in range(2, n):
      # 만약 소수가 아니면 소수여부 False 처리
      if n % i == 0:
        is_prime = False
    # 소수여부 확인된 값만 전달
    if is_prime:
      yield n

 

에라토스네테스의 체 방법 

2, 3, 5, 7, 11, 13 등 소수의 배수를 제외했을 때 남는 수를 찾는 방식

import math

def prime_number_generator(start, stop):
  n = stop
  # 구하고자 하는 수 만큼 True를 갖는 리스트 생성
  is_primes = [True] * n
  # n의 최대 약수가 sqrt(n) 이하이므로 계산한 후, 소숫점이 있을 경우 올림으로 최대 반복 횟수 계산
  max_length = math.ceil(math.sqrt(n))

  for i in range(2, max_length):
    # True일 경우, 소수
    if is_primes[i]:
      # i이후 i의 배수들을 지워나감
      for j in range(i+i, n, i):
        is_primes[j] = False

  # 리스트의 True로 남아있는 인덱스(소수)를 추출
  yield from [i for i in range(start, stop) if is_primes[i]]