[백준 python 4134] 다음 소수

[Silver IV] 다음 소수 - 4134

문제 링크

성능 요약

메모리: 33240 KB, 시간: 1456 ms

분류

브루트포스 알고리즘, 수학, 정수론, 소수 판정

제출 일자

2023년 12월 18일 23:34:21

문제 설명

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

입력

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

출력

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

import math
import sys
input = sys.stdin.readline

def prime(x):
    if x == 0 or x == 1:
        return False

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

n = int(input())
for _ in range(n):
    x = int(input())
    while True:
        if prime(x):
            print(x)
            break
        x += 1

풀이

소수를 판별할 수 있는 알고리즘을 사용해서 문제를 풀었는데 시간초과가 났다. 방법을 찾아보니 제곱근을 한 값도 소수 판별이 가능하다고 하여 이를 참고하여 문제를 풀어보려고 했다.

처음에 0과 1이었을 경우를 해결하지 않아 계속 틀렸다고 떴다. n은 0부터 나오기 때문에 소수가 아닌 0과 1은 제외해주어야 한다.