[파이썬 수학] 소수(prime number) 판별

중학교 1학년 교과과정의 시작은 소수를 찾는 것부터 시작합니다. 에라토스네스의 체를 이용하여 소수를 판별하는 법을 배우면서 2, 3, 5, 7, 11, ...로 이어지는 소수의 수열을 배웁니다.

오늘은 소수의 정의를 이용해서 파이썬으로 소수를 구별하는 코드를 만들어 보려 합니다.

여러분도 잘 아시다시피, 소수의 정의는 '1과 자기 자신 외에 양의 약수가 없는 1보다 큰 자연수'입니다.

따라서, 자연수 중에서 1은 소수가 아닙니다. 

 

2부터 소수가 될 자격이 있는데, 6과 같은 수는 1, 2, 3, 6을 양의 약수로 갖기 때문에 소수가 아닙니다. 6을 예로 들어서 설명하면, 6을 2부터 자신보다 1이 작은 수들인 [2, 3, 4, 5]로 나누어 보면, 나머지는 [0, 0, 2, 1]이 됩니다. 결국, 자연수 6은 [1, 6] 이외에도 [2, 3]으로 나누어도 나머지가 0이 되기 때문에 소수가 아닙니다.  

이번에는 자연수 5를 예로 들어보겠습니다. 5를 2부터 자신보다 1이 작은 수인 [2, 3, 4]로 나누어 보면, 나머지는 [1, 2, 1]이 됩니다. 자연수 5는 [1, 5] 이외에는 나누어도 나머지가 0이 되지 않기 때문에 [2, 3, 4]를 양의 약수로 갖지 않습니다. 따라서, 소수가 분명합니다.  

 

파이썬으로 소수를 판별하는 코드를 작성해 보겠습니다. 

 

def prime_number(number):   # number를 입력 받아 소수인지 아닌지 구분하는 함수
     # number가 1이 아니면, (1은 소수가 아님)
    if number != 1:                 
        # 2, 3, 4, ..., (number - 1)까지의 인수에 대해서
        for f in range(2, number):  
            # number가 위의 인수 중의 하나로 나누어지면, (나머지가 0이면)
            if number % f == 0:     
                return False    # 소수가 아님
    else:                       # number가 1이라면, 
        return False            # 소수가 아님
    
    # number가 1이 아니면서, 2부터 (number - 1)까지의 수로 나눠지지 않으므로
    # 소수로 판별됨 (소수는 1과 자신만을 인수로 갖는 수)
    return True                 

   
num = input("Input a number: ")
if prime_number(int(num)):
    print("TRUE: The input number " + num + " is a prime number.")
else:
    print("FALSE: The input number " + num + " is NOT a prime number.")

 

파이썬 코드를 실행하고 number로 20과 17을 입력하면, 20은 소수가 아니고 17은 소수라고 판별합니다. 오류 없이 잘 작성된 것 같습니다. 

 

Input a number: 20
FALSE: The input number 20 is NOT a prime number.

Input a number: 17
TRUE: The input number 17 is a prime number.