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

백준 > 소수 구하기

문제

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

입력

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

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입출력

입력	출력
3 16	3 5 7 11 13

 

---

👊 내 문제 풀이

직전에 푼 인프런 에라토스테네스 체 문제와 동일한 유형의 문제를 찾아서 풀어봤다.

n+1 크기의 리스트를 만들어 소수 판별을 한 결과 값을 반영한 후, m ~ n+1 구간에 있는 소수를 출력했다.

소수 판별 알고리즘은 이전의 에라토스테네스 체 문제와 동일하게 사용했다.

 

[참고] [인프런 - 파이썬 알고리즘 문제풀이] 2.7 소수(에라토스테네스 체)

m, n = map(int, input().split())
numList=[True]*(n+1)
numList[0] = False
numList[1] = False

for i in range(2, n+1):
    if numList[i] == True:    #True면 소수
        for j in range(i+i, n+1, i):  #소수 i의 배수들은 모두 제외(False)
            numList[j] = False

for i in range(m,n+1):
    if numList[i] == True:
        print(i)

 

채점 결과

 

처음엔 0, 1번째 인덱스에 대한 처리를 해주지 않아서 틀렸지만, 둘 다 False로 초기화한 후 재채점 하니 정답처리가 되었다.

 

에라토스테네스의 체