[백준 1929번] 소수 구하기 (파이썬/python)

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

1929번: 소수 구하기

 

에라토스테네스의 체를 이용해 간단하게 풀 수 있다.

1은 소수가 아니기때문에 미리 False값을 넣어줘야함에 유의하자~!

 

 

import sys
from math import sqrt
 
input = sys.stdin.readline
 
a, b = map(int, input().split())
li = [True for _ in range(b + 1)]
li[1] = False
 
# 에라토스테네스의 체
for i in range(2, int(sqrt(b)) + 1):
    if li[i] == True:
        j = 2
        while i * j <= b:
            li[i * j] = False
            j += 1
 
for i in range(a, b + 1):
    if li[i] == True:
        print(i)