[python] 백준 1929 소수구하기
문제
특정 수의 범위 내에 있는 소수를 모두 구하는 문제이므로, 에라토스테네스의 체로 푸는 문제이다. 메모리 제한 역시 256MB로 넉넉하고 범위도 백만까지이기 때문에 넉넉한 편이다.
풀이
import sys
input = sys.stdin.readline
m, n = map(int,input().split())
lst = [True for i in range(0,n+1)] n개만큼의 공간을 가진다.
def is_prime_number(n): #에라토스테네스의 채 함수
lst[0] = False # degenerate case인 0과 1은 False로 처리한다.
lst[1] = False
for i in range(0,n+1):
if lst[i] == True:
j = 2
while i * j <= n: #i의 배수면서 n 이하인 값은 모두 false(소수가 아님) 처리를 한다.
lst[i*j] = False
j += 1
is_prime_number(n)
for i in range(m,n+1): #채에서 True인 요소들만 출력
if lst[i]:
print(i)
else:
continue