소수 여부를 판별할 수 있는 함수를 작성해 보자.

참고로 숫자 1은 소수가 아니다!

 

def prime_num_classify(n):
    if n == 1:
        return False
    elif n in [2, 3, 5, 7]:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False
    else:
        for i in range(3, n // 2):
            if n % i == 0:
                return False
    return True
 

위 코드는 정상 작동하지만 숫자가 커질수록 비효율성이 커진다. chatGPT는 위 코드를 100점 만점에 50점으로 평가하였으며 이를 개선할 수 있는 90점짜리 최적화 코드를 제공하였다.

 

else 이후 부분을 주목해서 보자.

def prime_num_classify(n):
    if n == 1:
        return False
    elif n in [2, 3, 5, 7]:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False
    else:
        i = 5
        while i * i <= n:
            if n % i == 0 or n % (i + 2) == 0:
                return False
            i += 6
    return True
 

Breakdown

    else:
        i = 5

먼저 소수판별을 할 n의 인수(나누어줄 수)로 숫자 5부터 점검하기 시작한다. 왜 5부터 시작할까? 인수로 2, 3은 elif구문에서 이미 판별하였고, 4는 짝수라서 역시 elif구문에서 걸러졌기 때문이다.

        while i * i <= n:

인수의 제곱이 나누어지는 수(n)보다 작은 경우에만 이터레이션을 돌린다. 다르게 말하면, n의 제곱근 정수값 int(n ** 0.5) 보다 i가 작거나 같은 경우에만 이터레이션을 돌린다. 왜 그럴까?

 

We only need to test divisibility by potential factors up to the square root of n. This is because if n has a factor larger than its square root, it must also have a corresponding factor smaller than its square root.

 

우리는 i가 주어진 수(n)의 인수가 되는지, 즉 n이 i로 나누어 떨어지는지를 살펴 보며 소수를 판별한다. 이 때 i값은 n의 제곱근 정수값 int(n ** 0.5)까지만 살펴보면 되는데, 그 이유는 인수와 몫의 관계 때문이다. 아래 예시를 확인해 보면, 나눗셈을 할때 제곱근 정수를 기준으로 인수와 몫이 갈라지게 되는 것을 확인할 수 있다.

 

(예)

  1. 숫자 225의 약수는 [1, 3, 5, 9, 15, 25, 45, 75, 225]이다. 225의 제곱근 정수는 15이다. 15를 기준으로(225는 완전제곱수) 9 * 25 = 225와 같이 인수(9)와 몫(25)이 갈라지는 것을 확인할 수 있다.
  2. 숫자 108의 [1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108] 이다. 108의 제곱근 정수는 10이다. 10을 기준으로 9 * 12 = 108과 같이 인수(9)와 몫(12)이가 갈라지는 것을 확인할 수 있다.

 

따라서 제곱근 정수 이하의 숫자에 인수가 있는지만 확인하면 계산을 단축하여 효율성을 높일 수 있는 것이다. (9 * 12 = 108, 12 * 9 = 108과 같은 중복 계산을 제외하게 되는 것.)

 

만약 n = 119일 경우를 생각해 보자. i = 5부터 시작하면, i * i = 25이므로 True가 되어 if문을 살펴보게 된다.

            if n % i == 0 or n % (i + 2) == 0:
                return False
            i += 6
 

119은 5로 나누어지지 않는다.

119는 7로 나누어 떨어진다. (몫 : 17)

따라서 119는 소수가 아니므로 False를 리턴하고 함수가 종료된다.

 

그렇다면 if문에서는 왜 i + 2만 함께 점검하는 걸까?

  1. 우리가 점검해 줄 i값은 5에서 시작하여 2씩 늘려주면 된다. 왜냐면 홀수값만 판별하면 되니까. 주어진 숫자 n이 짝수로 나누어 떨어지는지는 그 전에 이미 확인을 했다. (elif 구문)
  2. i + 1, i + 3, i + 5 모두 짝수이기 때문에 확인할 필요가 없다.
  3. 그럼 i + 4는 왜 안해도 될까? i + 4의 경우 확인해 보면 3의 배수가 되는 것을 알 수 있다. 따라서 i + 6을 해준 다음 이터레이션을 돌리는 것이다. 이 과정을 통해 계산 시간을 줄이고 효율성을 높이게 되었다.

 

'Code > function snippet' 카테고리의 다른 글

python | numpy 라이브러리를 이용하여 최대공약수, 최소공배수 구하기 (gcd, lcm)  (0) 2024.04.08
python | 연속 공백 여러개 분리하기, split 함수 대신 정규식(re) 활용하기!  (0) 2024.04.08
python | 재귀함수 (팩토리얼 예제)  (0) 2024.04.01
python | 약수(factor) 리스트업 함수 작성하기 + 메모화 (memorization)  (0) 2024.04.01
python | 중첩리스트 평탄화 함수 작성하기 flatten function (+ 여러번 중첩되는 경우 : 재귀함수!!)  (0) 2024.04.01

+ Recent posts

티스토리툴바