개요
2022.06.18 - [Algorithm] 에라토스테네스의 체에서 정리한 에라토스테네스의 체 알고리즘은 소수를 찾는 방법으로 유명하다. 다만 범위 내의 모든 소수를 찾는 방법이기 때문에, 어떤 수가 소수인지 아닌지를 확인할 때는 효율적이지 않을 수 있다.
이 글에서는 어떤 수를 입력으로 받아, 그 수가 소수인지 아닌지를 판별하는 방법을 적어둔다.
접근
소수는 1과 자기 자신을 제외한 어떤 수로도 나누어 떨어지지 않는 수를 말한다.
어떤 수가 소수인지 아닌지 판별하기 위해서는 약수의 성질을 먼저 생각해봐야 한다.
약수는 제곱근을 기준으로 대칭을 이룬다. 따라서 어떤 수의 약수를 찾을 때 제곱근까지만 확인하면 나머지 약수는 자연스럽게 구할 수 있다.
즉, 어떤 수가 소수인지 아닌지를 판별하고 싶을 때는 2부터 제곱근까지의 수에 대해서 나누어 떨어지는 수가 있는지 확인하면 된다.
구현
자연수 n을 매개변수로 하는 소수 판별 함수를 구현은 다음과 같다.
1. 2 미만의 수는 소수가 아니다.
if n <= 1:
return False
2. n이 2부터 제곱근까지의 수에 대해 나누어떨어지면 소수가 아니다.
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
3. 만약 반복문을 전부 통과하면 소수이다.
즉, 전체 함수는 아래와 같다.
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
참고 문서
728x90