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

1. 링크

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

2. 난이도(solved.ac 참고)

실버5

3. 풀이

	# https://www.acmicpc.net/problem/4134
	import sys
	import math
	f = sys.stdin.readline
	def is_prime(x):
	if x == 0 or x == 1:
	return False
	for i in range(2, int(math.sqrt(x))+1):
	if x % i == 0:
	return False
	return True
	T = int(f())
	for i in range(T):
	z = int(f())
	while True:
	if is_prime(z):
	print(z)
	break
	else:
	z += 1

view raw 다음소수.py hosted with ❤ by GitHub

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

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

      

      

      

    
    

      <javascript />
    
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만 확인을 하게 된다.