고양이 두 잔

문제 정수 n(0 ≤ n ≤ 4*10^9)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. 출력 각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다. 풀이 Trial Division 방법은 정확하게는 소인수분해를 할 때 사용되는 방법이다. 증명이라기보다는 간단하게, 주어진 수 n을 x * y로 분해했을 때 둘 중 하나는 반드시 n의 제곱근보다 작거나 같다는 성질을 이용한 판별법이다. 에라토스테네스의 체(O(N log log N))에 비하면 속도가 느리지만(O(sqrt(n))), 적당히 작은 수에선 괜..