[python/파이썬] 백준 4134 다음 소수

문제

정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

출력

각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

3
6
20
100

예제 출력 1 복사

7
23
101

 

 

[소스 코드]

 

처음에는 3중 for문을 이용해서 코드를 짰다. 당연히 시간 초과가 뜰 거라고 생각했지만 그냥 한 번 해봤다.

역시나 시간초과가 뜨길래 함수를 정의해서 했는데 이번에도 시간 초과가 떴다.

아래 코드와 비슷한데 소수를 판별하는 함수에서 for문의 범위만 달랐다.

 

어떤 수 x가 소수인지 알기 위해서는 x보다 작은 숫자들로(1과 자기자신을 제외한 숫자들) 나눠봤을 때 나눠지는지 여부를 확인하면 된다. 따라서 range(2, x)로 설정하였는데 시간 초과가 떴다.

검사하는 횟수가 너무 많아지기 떄문이기에 범위를 줄여주었다.

 

2부터 하나씩 증가시켜가며 확인을 하다보면 확인할 필요가 없는 숫자들이 있다. 만약 2로 나눠졌다면 그 몫은 x보다 작을 것이고 2보다는 크거나 같을 것이다. 따라서 for문을 돌면서 그 숫자는 검사할 필요가 없는 것이다. 

 

16을 예시로 들면 약수는 1, 2, 4, 8, 16 이렇게 5개인데 4이후로는 검사하지 않아도 되는 값이다. 따라서 제곱근을 구하고 1을 더해서 제곱근까지만 검사하는 것이다.

만일 소수의 경우도 제곱근 이전의 값들에서 나눠지는 수가 없다면 제곱근 이후에도 존재하지 않는 것이기 때문에 제곱근까지만 검사해도 괜찮다.

import sys
import math #제곱근 구할 때 쓰임

data = sys.stdin.readline
n = int(data())

def is_prime(x): #소수를 판별하는 함수 정의
    if x<2: #0과 1은 소수에 포함되지 않음
        return False
    
    for i in range(2, int(math.sqrt(x))+1): #시간초과때문에 범위를 줄임
        if x%i == 0:
            return False
    return True

for i in range(n): #n번의 테스트 케이스
    x = int(data()) #같거나 큰 소수 찾기 이므로 x부터 시작
    while True:
        if is_prime(x): 
            print(x)
            break
        else:
            x += 1 #소수가 아니라면 1증가해서 검사