[파이썬] 백준 1929번 소수 구하기 문제 풀이

문제 설명

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

 

문제 링크

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

1929번: 소수 구하기

 

입출력 예시

 

프로그램 코드

import math

def is_prime(a):    #소수 구하는 함수
    if a == 1:
        return 0
    for i in range(2, int(math.sqrt(a)) + 1):   #2부터 그 숫자의 제곱근까지 검사
        if a % i == 0:
            return 0
    return 1

M, N = map(int, input().split())    #문제 입력

for i in range(M, N+1): #M 부터 N까지 소수인지 검사
    if is_prime(i):
        print(i)

 

프로그램 코드 설명

소수는 1과 자기 자신으로만 나누어지는 숫자를 뜻한다.

간단하게 생각하면 2부터 자기 자신 전까지 숫자 중 아무것으로도 안 나눠지면 소수가 된다.

하지만 이런 방식으로 계산을 하게 되면 프로그램 속도가 느려져서 이 문제는 런타임 에러가 난다.

18을 예시로 들어서 이해를 해보자.

18은

1 x 18

2 x 9

3 x 6

6 x 3

9 x 2

18 x 1

이런 식으로 곱셈이 가능하다.

다른 식으로 생각해보면 루트 18을 두 번 곱해도 18을 구할 수 있다.

따라서 루트 18 전까지 숫자들 중 약수를 찾으면 된다.

소수를 구할 때도 어떤 숫자의 제곱근 숫자까지만 검사를 하면 소수인지 판별을 할 수 있다.

위의 코드에서도 소수 검사를 해당 숫자의 제곱근까지만 진행을 한 것을 확인할 수 있다.

이렇게 소수를 구할 때 해당 숫자의 제곱근까지 소수 판별을 하면 실행시간을 줄일 수 있다.