[백준][1929] 소수 구하기

• 문제
  • 1929번: 소수 구하기
• 해설

import sys

minimum, maximum = [int(x) for x in sys.stdin.readline().split()]


def prime_candidate_generator_less_than(n):
    # 5, 7, 11, 13, 17, 19, ...
    candidate = 5
    increment = 2
    increment_changer = {2: 4, 4: 2}
    while candidate <= n:
        yield candidate
        candidate += increment
        increment = increment_changer[increment]


def get_primes_by_sieve_less_than(n):
    if n == 1:
        return []
    elif n == 2:
        return [2]
    elif n == 3:
        return [2, 3]
    else:
        prime_list = [2, 3]
        sieve_list = [True] * (n + 1)
        for candidate in prime_candidate_generator_less_than(n):
            if sieve_list[candidate]:
                prime_list.append(candidate)
                for i in range(2, 1 + (n // candidate)):
                    sieve_list[candidate * i] = False
        return prime_list


res = get_primes_by_sieve_less_than(maximum)
for i in res:
    if i >= minimum:
        print(i)

• 포인트
  • 에라토스테네스 체(sieve) 사용