[Algorithm] 소수 판정 (정수론)

완전 탐색으로 소수 탐색하면, 시간 초과가 발생하는 경우가 발생한다.

n 제한이 10^12 정도로 나오면 무조건 시간 초과이다.

📒 완전 탐색 코드 - 시간 초과

n = int(input())

cnt = 0 
for i in range(1,n+1):
    if n%i == 0:
        cnt +=1
        
if cnt == 2:
    print('YES')
else:
    print('NO')
   

😎 해결 방법

나누어 떨어지는 수가 있는지 확인하는 것이 소수판정이다.

나누어 떨어진다는 것은 현재 수를 a * b로 나타낼 수 있다는 건데 그러면 한 쌍으로 나오게 된다.

따라서 수의 제곱근 이하까지만 확인하면 된다.

제곱근까지 구해야하는 것이 포인트이다.

수가 1일 때 에러가 나지 않게 생각해줘야 한다.

📒 코드

n = int(input())

cnt = 0 
for i in range(1, n + 1):	# n이 1인 경우 에러가 나지 않도록 n + 1까지 확인한다.
    if i * i > n:		# 제곱근 이하까지만 확인하니 넘어가면 확인하지 않는다.
        break
    if n % i == 0:
        cnt += 1
        
if cnt == 2:
    print('YES')
else:
    print('NO')