[Python] BOJ(백준) 4134번 - 다음 소수

링크

https://www.acmicpc.net/problem/4134

난이도(solved.ac 참고)

실버5

풀이

while True 문에서 소수면 그 값을 print하고 아니면 값을 1 더해주고 다시 소수 여부를 판단하는 함수를 돌린다.

여기서 소수의 범위를 줄여줘야 했다.

def is_prime(x): if x == 0 or x == 1: return False for i in range(2, x): if x % i == 0: return False return True

이렇게 하면 시간초과가 뜬다. x까지 전부 다 돌기 때문에 시간이 상당해 오래 걸린다.
8을 예로 들어보자. 8의 약수는 1, 2, 4, 8이 있다. 근데 1 * 8 = 2 * 4이다. 즉 대칭을 이룬다는 것이다. 따라서, 해당하는 수의 제곱근을 구한 뒤 +1을 더한 값이라면 제곱근의 값까지의 범위가 된다. 그래서 원래는 x까지의 범위라면 2, 3, 4, 5, 6, 7을 전부 돌아야 하지만 이렇게 한다면 2만 확인을 하게 된다.