4134번: 다음 소수 (acmicpc.net)

##
소수 판별에서는 주어진 수 n의 제곱근까지만 확인해도 충분합니다. 이는 수학적 원리에 기반한 효율적인 방법입니다. 주어진 수 n이 소수인지 확인하려면, 2부터 √n까지의 숫자들로 나누어 떨어지는지 확인하면 됩니다. 그 이유는 다음과 같습니다:

만약 n이 어떤 두 수 a와 b의 곱으로 표현된다면 (n = a * b), 그 중 하나는 반드시 √n 이하입니다. 즉, a와 b 중 하나는 √n보다 작거나 같아야 합니다.
따라서 √n 이후의 숫자들은 이미 이전에 확인한 숫자들의 곱으로 표현될 수 있어서 굳이 확인할 필요가 없습니다.

그래서 O(√n)이 된다..

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

def find_min_prime(n):
    if n==0 or n==1:
        return 2

    num = n
    while(True):
        if is_prime(num):
            return num
        else:
            num += 1

for _ in range(int(input())):
    print(find_min_prime(int(input())))

0,1일때 예외처리 해야함