[Prime Number] 백준 1929번 “소수 구하기” Python 풀이

문제 링크

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

풀이

• 에라토스테네스의 체를 이용해야하는 대표적인 문제입니다.
• m의 값이 최소 1인 것을 주의해야하며,
• n의 값이 최대 1000000인 것을 주의해야합니다.
• 또한, 소수 탐색 시, n의 제곱근까지만 탐색을 진행한다면 실행 시간을 단축시킬 수 있습니다.

코드

import sys
import math

# m과 n 입력
m, n = map(int, sys.stdin.readline().split())

# 소수 판별 결과를 저장하기 위한 리스트 초기화
# 처음에는 모든 수가 소수인 것으로 초기화
array = [True] * (1000001)

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

# 2부터 n의 제곱근까지 에라토스테네스의 체 진행
for i in range(2, int(math.sqrt(n))+1):
    # i가 아직 남아있는 소수인 경우
    if array[i] == True:
        # i를 제외한 i의 모든 배수를 제거하기
        j = 2
        while i * j <= n:
            array[i * j] = False
            j += 1

# m 이상 n 이하의 소수를 모두 출력
for i in range(m, n+1):
    if (array[i] == True):
        print(i)