[백준] 4134번 다음 소수

💡문제접근

• 문제에 주어진 값의 범위를 보고 에라토스테네스의 체를 사용할지 아니면 일반적인 소수 판별 알고리즘을 사용할지 판단할 수 있어야 한다.
• 이 문제에서 주어진 n의 값의 범위는 0 ≤ n ≤ 4×10^9이다. 에라토스테네스의 체를 사용할 경우 메모리 초과가 발생한다.

📌 소수 판별 알고리즘에서 주의할 내용 정리

①. 0과 1은 합성수도 소수도 아니다. 코너 케이스로 분류되므로 이 케이스를 별도로 넣어 소수 판별 알고리즘의 완성도를 높인다.
②. 문제에서 주어진 메모리와 시간을 고려하여 어떤 방법을 써야할지 바로바로 떠올려야한다.
③. 소수 판별 알고리즘을 구현하는 과정에서 탐색 시간과 범위를 줄이기 위해서 제곱근의 개념을 이용한다.

💡코드(메모리 : 31256KB, 시간 : 1424ms)

import sys
input = sys.stdin.readline

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

T = int(input())
for _ in range(T):
    n = int(input())

    while True:
        if n == 1:
            n += 1
        if isprime(n):
            print(n)
            break
        n += 1

💡소요시간 : 8m