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

문제 (링크)

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

1929번: 소수 구하기

나의 풀이

import math

m, n = map(int, input().split())
arr = [True for _ in range(n+1)]

for i in range(2, int(math.sqrt(n)) + 1):
	if arr[i] == True:
    	j = 2
        while i * j <= n:
        	arr[i*j] = False
            j += 1

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

 

접근 방법 및 코드 설명

 

낮에 공부했었던 에라토스테네스의 체를 사용하는 문제이다. (seongonion.tistory.com/43)

 

범위인 m과 n이 무엇이든지 간에 해당 수가 소수인지 아닌지를 저장하는 배열 arr은 n+1의 길이까지 만들어줘야 한다.

 

또한, 모든 수에 대한 검사를 할 필요 없이, n의 제곱근까지만 검사를 진행하면 그 뒤의 값들은 자동으로 처리가 된다.

 

중요한 점은, 입력 케이스로 m이 1로 주어질 수 있는데, 기존 아레토스테네스의 체 함수는 입력값에 1이 올 수 없다는 걸 전제로 짜여지기 때문에, 출력 코드에서 i가 1이 올 경우일 때를 위한 별도의 처리를 해주어야 한다.

 

내 코드에서 처럼 마지막 출력에서 i > 1 이라는 조건을 달아줄 수도 있고, 애초에 arr을 정의할 때 arr[1] = False 로 처리하는 등의 작업을 수행할 수 있겠다.