[BOJ] 1929 소수 구하기 (Python / 파이썬)

🧷 문제

https://www.acmicpc.net/problem/1929

M이상 N이하의 소수를 모두 출력하는 문제이다.

🛠 풀이

이 문제는 '에라토스테네스의 체' 를 이용해 해결할 수 있다.

Step 1.
 에라토스테네스의 체를 이용해 소수를 판별한다.

• 에라토스테네스의 체
  : 소수를 판별할 범위만큼 배열을 할당하고 그 인덱스에 해당값을 넣어준 후에, 2부터 시작해서 그 값이 True라면 그 수의 배수에 해당하는 숫자들을 모두 False로 바꿔주는 것을 반복해 대량의 소수를 한꺼번에 판별하는데 용이한 알고리즘이다.
  

  

🖊 나의 코드

import sys

input = sys.stdin.readline

def is_prime(x, y):
    prime_num = [True] * (y+1)

    for i in range(2, int(y**0.5)+1):
        if prime_num[i] == False:
            continue

        for j in range(2*i, y+1, i):
            prime_num[j] = False

    for idx in range(x, y+1):
        if idx <= 1:
            continue
        if prime_num[idx] == True:
            print(idx)

if __name__ == "__main__":
    m, n = map(int, input().split())
    is_prime(m, n)