문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
<코드>
import sys
import math
input = sys.stdin.read
M, N = map(int, input().split())
# 에라토스테네스의 체를 사용한 소수 판별
is_prime = [True] * (N + 1)
is_prime[0] = is_prime[1] = False # 0과 1은 소수가 아님
for i in range(2, int(math.sqrt(N)) + 1):
if is_prime[i]:
for j in range(i * i, N + 1, i):
is_prime[j] = False
# M 이상 N 이하의 소수 출력
for num in range(M, N + 1):
if is_prime[num]:
print(num)
<풀이과정>
-is_prime = [True] * (N + 1): N까지의 숫자를 소수로 가정하고 초기화
-is_prime[0] = is_prime[1] = False: 0과 1은 소수가 아니므로 False로 설정
-에라토스테네스의 체 적용:
-2부터 N의 제곱근까지 반복
-i가 소수인 경우, i의 배수들을 False로 설정
*에라토스테네스의 체 원리
- 숫자 배열 생성: 2부터 N까지의 숫자를 나열
- 소수 판별 시작: 배열의 첫 번째 숫자(2)를 소수로 간주하고, 그 배수들을 모두 삭제
- 다음 숫자로 이동: 배열에서 지워지지 않은 다음 숫자를 소수로 간주하고, 그 배수들을 모두 삭제
- 반복: 이 과정을 N의 제곱근 이하의 숫자에 대해 반복
- 배열에서 지워지지 않은 숫자들이 모두 소수가 됨
'2024 코딩테스트 스터디' 카테고리의 다른 글
[6주_7일차] 백준-2309 일곱 난쟁이(Python) (1) | 2024.07.15 |
---|---|
[6주_6일차] 백준-6588 골드바흐의 추측(Python) (0) | 2024.07.14 |
[6주_4일차] 프로그래머스-가운데 글자 가져오기(Python) (0) | 2024.07.12 |
[6주_3일차] 프로그래머스-핸드폰 번호 가리기(Python) (0) | 2024.07.11 |
[6주_2일차] 프로그래머스-제일 작은 수 제거하기(Python) (0) | 2024.07.10 |