[BOJ][Python] 4134 다음 소수

[문제]

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

4134번: 다음 소수

 

[코드]

범위가 매우 커서 x를 다 돌면 시간초과가 발생한다. 

제곱근 이하까지만 돌면서 소수인지 확인한다. 

#S4_4134 다음 소수.py

import sys
input = sys.stdin.readline

#isPrime
def isPrime(x):
    if x == 0 or x == 1:
        return False
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True
    
#main
T = int(input())
for i in range(T):
    n = int(input())
    while True:
        if isPrime(n):
            print(n)
            break
        else:
            n += 1

 

시간복잡도의 늪 T^T