[ 알고리즘 ] 파이썬으로 소수 구하는 프로그램 만들기, 파이썬 소수

[ 소수란? ]

소수란 

1보다 큰 자연수 중

1과 자기 자신만을 약수로 가지는 수

입니다.

 

예를들어

숫자 5는 약수를 1과 5

즉 1과 자기 자신만을 약수로 갖고 있으므로

소수입니다.

 

숫자 4의 약수는 1, 2, 4 이므로

소수가 아닙니다.

 

[ 소스코드 ]

def is_prime(n):
    if n < 2 :
        return "소수가 아닙니다."
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return "소수가 아닙니다."
    return "소수입니다."

print(is_prime(5))

 

[ 코드설명 ]

여기부터는 관심있으신 분들께서만 보시면 될 것 같습니다.

728x90

반응형

SMALL

 

is_prime(n) 함수는

숫자를 입력 받아 소수인지를 확인하는 함수입니다.

 

먼저 소수는 1보다 큰 자연수 중에 존재하므로

2 미만의 수는 소수가 아닙니다.

    if n < 2 :
        return "소수가 아닙니다."

 

다음 구문을 보시기 전에

만약 range() 함수를 모르신다면 여기를 먼저 확인하시기 바랍니다.

 

아래 코드는 소수를 구하는 가장 중요한 코드입니다.

    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return "소수가 아닙니다."

 

위 코드는 숫자 2부터 

입력받은 값의 0.5 거듭제곱을 한 뒤 1을 더한 수까지

반복을 합니다.

0.5 거듭제곱은 수학의 루트와 같습니다.

range() 함수의 특성때문에 [ +1 ]을 하게 됩니다.

그리고 그 숫자 중 하나로 나누어지게 되면

그 숫자는 소수가 아니게 됩니다.

 

그리고 어떠한 수로도 나누어 지지 않으면

소수이게 됩니다.

 

range(2, int(n**0.5)+1)는 

소수 판별 알고리즘의 효율성을 높이기 위한 코드입니다.

소수를 판별할 때,

2부터 n까지의 모든 수로 n을 나누어 보는 방법은 비효율적입니다.

왜냐하면 n이 소수가 아니라면,

그 약수는 반드시 √n 이하에 존재하기 때문입니다.

 

예를 들어,

36의 약수를 생각해보면 [ 1, 2, 3, 4, 6, 9, 12, 18, 36 ]이 있습니다.

이 중 √36인 6 이상의 약수(9, 12, 18, 36)는

모두 다른 약수(4,3,2,1)와 곱해져서 36이 되므로,

√n 이하의 수만 검사해도 충분합니다.

 

따라서 range(2, int(n**0.5)+1)는 

2부터 √n까지의 범위를 생성하여 

n이 소수인지 판별하는 데 필요한 연산을 줄입니다. 

이렇게 하면 특히 큰 수에 대해 소수를 판별할 때 

시간을 크게 절약할 수 있습니다.

 

def is_prime(n):
    if n < 2 :
        return "소수가 아닙니다."
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return "소수가 아닙니다."
    return "소수입니다."

print(is_prime(12345679879864564654654))

 

[ 12345679879864564654654 ] 라는 숫자는 소수가 아니라고 합니다.

[ 1112231232133333377773 ] 라는 숫자도 소수가 아니라고 합니다.