[Algorithm] 백준 4134번 다음 소수 (Python)

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

4134번: 다음 소수

문제

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

입력

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

출력

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

예제 입력 1

3
6
20
100

예제 출력 1

7
23
101

풀이

설명

• 소수를 구할 때 2부터 A까지 전부 돌면 너무 오래 걸려서 시간초과가 발생한다.
  • 따라서 '에라토스테네스의 체'를 사용하여 소수의 범위를 줄인다.
• 만일 해당 수가 소수이면 그 수를 출력하고 아니면 1씩 증가하여 다시 소수 검사를 한다.

코드

import sys

input = sys.stdin.readline

def prime(A: int):
    if A < 2:
        return False
    for i in range(2, int(A**0.5) + 1):
        if A % i == 0:
            return False
    return True

n = int(input())

for i in range(n):
    num = int(input())

    while True:
        if prime(num):
            print(num)
            break
        else:
            num += 1