[백준] 4134: 다음 소수 - 파이썬[python]

풀이

• 처음에 소수를 저장하는 리스트(set)을 만들까 했는데 n이 4*10^9까지 가능해서 이건 아니라는 걸 알게 됐다.
• 시간을 줄이는 방법이 뭐가 있을까 고민했지만,, 실패했고 구글링으로...
• 에라토스테네스의 체라는 방법을 써서 소수를 직접 찾는다.
• 대신, 약수를 구할 때처럼 나누어지는 수를 찾는 개수를 줄인다!
• 약수는 항상 대칭이다. 예를 들어, 36의 약수는 (1, 36), (2, 18), (3, 12), (4, 9), (6, 6)으로, 6을 기준으로 대칭된다.
• 그러므로 대칭되는 마지노선(?)은 √N이라 해당 수가 나누어지는지를 2부터 √N까지만 확인해보면 된다.

코드

import sys, math

def isPrime(num):
    if num == 0 or num == 1:
        return False
    for i in range(2, int(num**(1/2))+1): # math.sqrt(n)
        if num % i == 0:
            return False
    return True

n = int(sys.stdin.readline())

for _ in range(n):
    num = int(sys.stdin.readline())
    while True:
        if isPrime(num):
            print(num)
            break
        else:
            num += 1

• 제곱근은 num**(1/2) 또는 math.sqrt(n)로 표현할 수 있다.
• 주의할 점은 둘 다 실수로 출력되기 때문에 정수로 바꾸어 주어야 한다.
• 또한 문제 조건에서 n이 0부터 가능하기 때문에 입력받은 테스트 값이 0이나 1일 때도 검사를 해주어야 한다. 애초에 0과 1은 소수가 아니기에 이 입력값은 False를 반환하면 된다.

결과