[python] 소수(prime number) 판별하는 방법

소수(prime number) 란?

소수란 자기 자신과 1을 약수로 가지고 있는 수를 의미합니다. 다시 말하면, 약수가 2개밖에 없는 거죠.

ex) 2, 3, 5, 7, 11, 13, 17, 19, ... 

등이 있습니다.

 

수학에서 소수 판별법이란?

수학에서 소수 판별법이란, 자기 자신의 양의 제곱근 값을 기준으로, 보다 작은 수들로 나누어보며 판별합니다.

ex) 101 은 101의 양의 제곱근은 10.xxx 이므로 2, 3, 4, 5, 6, 7, 8, 9, 10 으로 101을 나눠봅니다.

2~10까지 101이 나눠지지 않으므로 101은 소수입니다.

 

파이썬에서 소수 판별하는 코드는?

def is_prime(num):
    if num <= 1:                  # 1 이하의 숫자는 소수가 아님
        return False
    for i in range(2, num):       # range(2,num)은 2부터 num-1까지
        if num % i == 0:          # % 는 num을 i로 나눴을 때 나오는 나머지를 구하는 연산자
            return False          # 소수가 아니면 False 반환
    return True     
    
print(is_prime(101))   # 101 테스트

 파이썬에서는 range 함수를 가지고, 2부터 자기자신 바로 전까지의 숫자로 하나라도 나눠떨어지면 False 를 반환해주게끔 코드를 작성해봤습니다.

소수는 1과 자기 자신, 즉 2개만은 약수로 가져야 하니깐요. 반대로 말하면, 1과 자기 자신을 제외한 그 어떠한 약수도 가져선 안됩니다. 이 원리를 이용하여 작성하였습니다.

 

감사합니다.