Primality Test

개요

소수는 과 자기 자신만을 약수로 갖는 수를 뜻합니다. 자연수 이 소수인지 빠르게 판별하는 법을 알아봅시다.

정의에 맞게 부터 까지 나누어떨어지는지 확인해 보면 됩니다. 단, 은 소수가 아니므로 예외처리 해 줘야 합니다.

def is_prime(n: int) -> bool:
    if n == 1:
        return False
 
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

이 로 나누어떨어진다면 로도 나누어떨어집니다. 이때 를 만족하는 자연수 의 범위는 이므로 까지만 테스트 해도 됩니다.

def is_prime(n: int) -> bool:
    if n == 1:
        return False
 
    for i in range(2, int(n ** (1/2)) + 1):
        if n % i == 0:
            return False
    return True

문제

1978번: 소수 찾기 풀이