[Python/파이썬] 백준 4134번 다음 소수

4134번: 다음 소수

 

코드

from math import sqrt


def prime(num):  # 소수인지 판별
    if num == 0 or num == 1:
        return False
    for i in range(2, int(sqrt(num))+1):
        if num % i == 0:
            return False
    return True


for _ in range(int(input())):
    n = int(input())
    for i in range(n, 5*int(1e9)):
        if prime(i):
            print(i)
            break

 

소수 판별이라길래 에라토스테네스의 체를 쓸까 했는데 범위를 보니까 택도 없어보였다.

 

그래서 n부터 1씩 키워가며 그 수가 소수인지 아닌지 판별하는 완전탐색 방법으로 코드를 짰다.

 

근데 여기서 문제는 소수인지 판별할 때, num이 소수인지 판별하려는 수라고 할 때 2부터 num-1까지 모든 수를 다 나눠보면 너무 오랜 시간이 걸린다는 것이다. 근데 우리는 어떤 수가 소수인지 판별하려할 때 그 수보다 작은 모든 수를 나눠볼 필요는 없다. 왜냐하면 약수들은 어차피 쌍을 이뤄서 그 수를 만들기 때문이다.

예를 들어, 10은 2*5로 표현할 수 있다. 여기서 10을 5로 나눠보지 않아도 이 수는 이미 2에서 소수가 아님을 알 수 있다. 그렇기 때문에 모든 수는 그 수의 제곱근까지만 나눠보면 소수인지 아닌지 판별할 수 있다.