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

문제 링크

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

1929번: 소수 구하기

 

문제

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

 

입력

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

 

출력

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

 

예제 입력

3 16

 

예제 출력

3
5
7
11
13

 

문제 풀이 및 코드

문제를 접근할 때 소수인지 판별하는 함수를 작성하고, 반복문을 통해 m부터 n까지의 증가하는 모든 수를 작성한 소수 판별 함수로 적용하여 소수일 때마다 출력하는 방법을 생각하였습니다. M과 N의 범위가 매우 크기 때문에 시간 초과가 나오지 않기 위해 효율적으로 소수를 판별하는 것이 중요합니다.

 

소수 판별하기

import math
 
def is_Prime_number(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                return False
        return True

math 라이브러리를 통해 제곱근을 구하는 math.sqrt() 함수를 사용하여 소수를 판별할 때 효율적으로 판별할 수 있도록 해야 합니다. is_Prime_number() 함수의 입력값 num의 제곱근을 구하여 2부터 num의 제곱근까지 나누어 떨어지는 수가 존재하면 num은 소수가 아니므로 False를 반환하고, 존재하지 않으면 소수임을 판단하여 True를 반환합니다.

또한, M이 1인 경우 에러가 발생할 수 있으므로 함수의 입력 값이 1인 경우 False를 반환하도록 합니다.

 

최종 코드

import math
 
def is_Prime_number(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                return False
        return True
 
m, n = map(int, input().split())
 
for i in range(m, n + 1):
    if is_Prime_number(i):
        print(i)

함수를 작성한 뒤 문제의 입력 값을 받아 반복문을 통해 m부터 n+1까지의 모든 수를 작성한 is_Prime_number() 함수를 통해 소수를 판별합니다.

함수의 리턴 값이 True와 False이므로 True일 경우에만 해당하는 i 값을 출력합니다.

 

본 코드는 제가 직접 작성한 것으로 더 나은 코드가 존재할 수 있으니 참고하시기 바랍니다.