[백준 문제풀이] 1929 - 소수 구하기

백준 문제풀이 1929번

풀이

‘M과 N이하의 소수’라는 문장을 보고 에라토스테네스의 체를 써서 풀이해야겠다고 생각했다.

1. 배열을 0,1 을 제외하고 n이하의 True를 담은 배열을 만듬(0, 1은 소수가 아니므로)

2. 에라토스테네스의 체 알고리즘으로 배열의 요소를 검사함

3. 출력함

코드

import sys

input = sys.stdin.readline


def prime_number(m, n):
    primes = [False, False] + [True] * (n - 1)  # 0,1은 False

    for i in range(2, int(n ** (0.5) + 1)):
        if primes[i] == True:
            for j in range(i * 2, n + 1, i):  # i*2 부터 n+1까지 i 단위로 반복함
                primes[j] = False

    for index in range(m, n + 1):
        if primes[index]:
            print(index)


m, n = map(int, input().split(" "))

prime_number(m, n)