[Baekjoon]백준 4134 다음 소수(실버 4) - Python

문제설명

문제를 읽어보면 입력받은 수보다 크거나 같은 수 중에서 가장 작은 소수를 찾는 문제이다

소수란 약수로 1과 본인 자신만을 가지는 수이다

이를 확인하기 위해서 그 수보다 작은 수를 나누어가며 나누어떨어지는지 확인해야하는데, 

생각해보면 굳이 소수를 확인할 때 모든 수를 나누어볼 필요는 없다

왜냐하면 확인하는 수의 제곱근의 크기보다 큰 수로 나누어 떨어지지 않기 때문이다

 

이해가 안 될수도 있으니 예시를 통해 확인해보자

예를 들어 49라는 숫자가 존재할 때, 7까지만 확인해보아도 문제가 없다

제곱근보다 큰 수로 나누어떨어지려면 반드시 그 짝수(즉, 제곱근 이하의 수)로도 나누어떨어지기 때문이다

좀 더 쉽게 설명하면, 만약 어떤 숫자 N이 a와 b라는 두 수의 곱으로 표현될 수 있다면,

이때 a와 b 중 최소 하나는 N의 제곱근 이하임을 확인할 수 있다

따라서 제곱근까지만 나누어보고 나누어떨어지는 숫자가 없다면 그 수는 소수라는 것을 판단가능하다

 

이를 적용하여 코드를 작성하면 된다

단, 주의할 점이 존재한다 문제를 다시 읽어보면 n의 범위가 0부터 시작하기 때문에 0과 1에 대한 검사도 존재해야 한다

그 검사가 존재하지 않는다면 필자처럼 틀렸습니다 라는 문구를 보게 될 것이다..

n = int(input())

for _ in range(n):
    prime = int(input())   
    while True:
        if prime == 0 or prime == 1:
            Is_prime = False    
        else:
            Is_prime = True
        for i in range(2, int(prime ** 0.5) + 1):
            if prime % i == 0:
                Is_prime = False
                break
        if Is_prime:
            print(prime)
            break
        else:
            prime += 1

기존의 코드는 if prime == 0 ~ Is_prime = True 부분이 존재하지 않아서 틀렸었다

이런 유형의 문제를 풀 때에는 항상 주의해야한다... ㅜ