백준 1929번. 소수 구하기 (Python / 파이썬)

문제

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

입력

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

출력

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

---

문제 풀이

M과 N이 주어졌을 때 M이상 N이하의 소수를 출력하는 문제입니다.

즉, M이상 N이하의 수들이 소수인지 아닌지 

판단하는 과정이 필요합니다.

 

수가 소수인지 아닌지 판단하기 위해 check 배열을 만들어주었습니다.

check 배열은 초기값으로 True를 가지고 있습니다.

1은 소수가 아니므로 1번째 배열은 False로 만들어줍니다.

2부터 반복분을 실행하여 해당 index의 배수들을 False로 만들어줍니다.

왜냐하면 어떤 수의 배수는 소수가 아니기 때문입니다.

 

이 과정을 모두 반복 한 뒤, M이상 N이하의 index를 가진 배열의 값이

True라면 소수라는 것이므로 해당 index를 출력하도록 해주었습니다.

---

My Code

check = [True] * 1000001 # 소수인지 판별할 list
check[1] = False # 1은 소수가 아니므로 False
for i in range(2, 1000001):
    for j in range(i + i, 1000001, i): # 배수들은 소수가 아니므로
        check[j] = False               # False로 바꿔줌

m, n = map(int,input().split()) # 자연수 m과 n

for i in range(m, n + 1): # m이상 n이하의 수 중
    if check[i]: # 소수라면 출력
        print(i)