[Python]4134번, 소수 판별법, Trial Division

문제

 

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

 

입력

 

첫째 줄에 테스트 케이스의 개수가 주어진다. 

각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

 

출력

 

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

 

풀이

 

Trial Division 방법은 정확하게는 소인수분해를 할 때 사용되는 방법이다.

 

증명이라기보다는 간단하게, 주어진 수 n을 x * y로 분해했을 때 둘 중 하나는 반드시 n의 제곱근보다 작거나 같다는

 

성질을 이용한 판별법이다.

 

에라토스테네스의 체(O(N log log N))에 비하면 속도가 느리지만(O(sqrt(n))),

 

적당히 작은 수에선 괜찮은 효율을 보인다고 한다.

 

나도 자바로 문제풀이를 할 때 에라토스테네스의 체를 구현한 적은 없으니까..

 

어쨌거나 앞으로 자주 쓰일지도 모르니 아예 소수 판별 함수를 구현해 놓고 그걸 가져다 썼다.

import sys
import math

t = int(sys.stdin.readline())


def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n) + 1)):
        if n % i == 0:
            return False
    return True


for _ in range(t):
    n = int(sys.stdin.readline())
    while not is_prime(n):
        n += 1
    print(n)