[백준 4134] 다음 소수 (python)

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

4134번: 다음 소수

다음 소수 문제

n보다 크거나 같은 소수 중에서 가장 작은 소수를 찾는 문제

에라토스테네스의 체를 이용해서 풀 수 있었다

📌 문제 접근 포인트

1. n보다 크거나 같은 소수를 찾아야 하므로, n이 소수인지 아닌지 판별하고 +1씩 늘려가도록 알고리즘을 고려해보자.
2. 소수를 판별하는 과정에서 숫자가 굉장히 크므로 에라토스테네스의 체를 이용해서 빠르게 찾아내주고, 이를 활용하여 소수 판별을 해주자.
3. 소수를 판별하는 과정에서 n의 제곱근 만큼 탐색을 진행하게 되는데, 여기서 math함수를 쓴 math.sqrt(n)을 쓰거나 int(n**0.5)를 사용하면 되는데, 여기서 주의할게 int(n**1/2)로 작성해버리면 1/2에 대한 연산이 더 들어갔다고 시간 초과가 떠버리는 일이 발생한다. 꼭 0.5나 math함수를 써주자.  

⚙️ 내가 푼 정답 코드

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

import sys, math
T = int(sys.stdin.readline())
for _ in range(T):
    n = int(sys.stdin.readline())
    while True:
        if prime(n):
            print(n)
            break
        else:
            n += 1