[Python] 백준 / 소수 구하기 / 1929번 / 에라토스테네스의 체

문제

소수 구하기 문제 링크

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

3 16

출력

3
5
7
11
13 

접근 방식

1. M+1 크기의 에라토스테네스 체 리스트를 만든다 (초기값 True, index를 수로 사용하기 위해)
2. 2부터 m^0.5 까지 본인을 제외한 배수를 False로 바꾼다
3. N부터 M까지 리스트 안에 True값을 가진 index를 출력한다

코드

def eratos(m):
    era = [True] * (m + 1) # index값을 1씩 올려 쓰기 위해
	
    # 2부터 m의 제곱근값 까지 
    for i in range(2, int(m**0.5) + 1):
    	# i 가 소수일 때 (소수가 아닌 값의 배수계산을 하지 않아도 됨)
        if era[i] == True:
            # i 값의 배수는 소수가 아님
            for j in range(i * 2, m + 1, i):
                era[j] = False

    era[1] = False # 1은 소수가 아님 

    return era

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

era = eratos(m)

# n부터 m까지 소수를 출력
for i in range(n,m+1):
    if era[i] == True:
        print(i)