(백준 알고리즘 문제풀이) 4134번 다음 소수

문제

문제 링크

 

문제 접근

• 에라토스테네스의 체를 사용하기에는 n의 범위가 4 * 10^ 9이기 때문에 적합하지 않다. 그렇기 때문에 일반 prime number을 구하는 함수를 만들어 사용한다.
• 만든 함수에서 n보다 크거나 같은 수 중 프라임넘버를 찾고 break포인트를 걸어준다.

코드

import sys, math
input = sys.stdin.readline


def is_prime_number(number):
    if number <= 1:
        return False

    if number % 2 == 0:
        if number == 2:
            return True
        return False

    for i in range(3, int(pow(number, 0.5)) + 1, 2):
        if number % i == 0:
            return False
    return True


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

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