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

문제 링크

https://www.acmicpc.net/problem/1929

문제

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

입력

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

출력

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

예제

입력

3 16

출력

3
5
7
11
13

---

정답 및 풀이

import sys
input = sys.stdin.readline

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

for i in range(m, n + 1):
    if i < 2:         
        continue
    for j in range(2, int(i**0.5) + 1):
        if i % j == 0:
            break
    else:
        print(i)

1. import sys
   • 빠른 입력을 사용하기 위해 sys 모듈을 불러온다.
2. input = sys.stdin.readline
   • 기본 input()보다 빠른 입력 방식으로 설정한다.
3. m, n = map(int, input().split())
   • M과 N을 입력받아 정수로 저장한다.
   • 문제 조건: M 이상 N 이하 범위의 소수를 출력해야 한다.
4. for i in range(m, n + 1):
   • M부터 N까지 모든 숫자 i를 검사한다.
   • n + 1 을 써야 N도 포함된다.
5. if i < 2:
   • 0과 1은 소수가 아니므로 바로 건너뛴다.
6. for j in range(2, int(i**0.5) + 1):
   • i의 약수를 찾기 위해 2부터 √i 까지만 검사한다.
   • √i 이상은 검사할 필요가 없다.
7. if i % j == 0:
   • i가 j로 나누어떨어지면 i는 소수가 아님 → 바로 break.
8. else: (for문의 else)
   • for문이 끝까지 진행되었고 break가 한 번도 없었다면
   • i는 어떤 수로도 나누어지지 않은 소수이다.
9. print(i)
   • 소수로 판별된 i를 출력한다.

---