문제

image

특정 수의 범위 내에 있는 소수를 모두 구하는 문제이므로, 에라토스테네스의 체로 푸는 문제이다. 메모리 제한 역시 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

 결과

image