4134. 다음 소수 (시간초과)

다음 소수 문제 바로가기

문제

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

입력

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

출력

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

문제 접근

def IsPrime 후 for문으로 하나하나 소수인지 확인하다가 소수이면 출력

첫번째 풀이 > 시간초과

import sys
input = sys.stdin.readline

def IsPrime(a):
    k = 0
    for i in range(int(a**0.5)):
        if a%(i+1) == 0:
            k += 1
    if k == 1:
        return 1
    else:
        return 0


N = int(input())
for i in range(N):
    num = int(input())
    while True:
        if IsPrime(num) == 1:
            print(num)
            break
        else: 
            num += 1

추가 메모

• 소수를 구할 땐 항상 (제곱근 + 1)꼴로 구해서 for문의 반복 수를 줄이는 것이 시간 초과를 방지할 수 있다.