[정수론] ChatGPT가 뱉어낸 소수판정 알고리즘을 분석해보자!

얼마 전에 ChatGPT를 사용할 일이 있어서 가지고 놀다가 우연히 소수판정 알고리즘을 알려달라고 했는데 다음과 같은 코드를 뱉어냈다.

def is_prime(num):
    if num <= 1:
        return False
    if num <= 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return False
        i += 6
    return True

print(is_prime(17))  # 17이 소수라면 True 반환

???

6씩 더하고... $i, i+2$로 나눈 나머지를 확인하네?

 

처음 보는 코드에 정확한지 의심이 들었고 원래 알고있던 알고리즘과 비교해보니 정확히 일치했다. 아래는 비교한 코드이다.

def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**.5)+1):
        if n % i == 0:
            return False
    return True

 

늘 보던 코드와 다르고 원래 쓰던 코드보다 더 빨라보여서 분석을 시도해봤다.

코드 분석

if num <= 1:
    return False
if num <= 3:
    return True

우선 1은 소수가 아니고 2,3은 소수이므로 위와 같은 분기를 한 것 같다.

if num % 2 == 0 or num % 3 == 0:
    return False

짝수는 소수가 아니고 3의 배수도 소수가 아니므로 미리 뺀 것 같다.

i = 5
while i * i <= num:
    if num % i == 0 or num % (i + 2) == 0:
        return False
    i += 6

이 코드가 핵심인 것 같다. 원래 코드는 $2, 3, 4, ..., \sqrt{N}$까지 나머지를 확인하는데 이 코드는 $5, 7, 11, 13, 17, 19, ..., \sqrt{N}$만 확인한다. 여기서 짝수는 따질 필요가 없으므로 제거하고 홀수로만 나눈 나머지를 확인하면 되기 때문에 $3, 5, 7, 9, 11, ..., \sqrt{N}$만 확인하면 된다.

그런데 여기서 3의 배수를 미리 제거했으므로 $5, 7, 11, 13, 17, 19, ..., \sqrt{N}$만 확인하면 된다. 

이 방법을 사용하면 $O(\frac{\sqrt{N}}{3})$이 된다. 원래의 코드 $O(\sqrt{N})$에서 짝수만 확인해도 $O(\frac{\sqrt{N}}{2})$보다 더 빠른 방법이 된다.

실제로 시간을 측정해보면 더 빠른 것을 알 수 있다. 

 

물론 밀러라빈이나 AKS같은 훨씬 빠른 알고리즘이 존재하고 위의 코드가 어딘가에 존재하는 코드였겠지만 ChatGPT가 이런 지식을 알고 있다는 것이 정말 놀라웠다. 나중에 기존 지식을 재조합하여 세상에 존재하지 않는 알고리즘을 만들어낸다면 인간을 뛰어넘는 AI가 될 것 같다. (그때되면 좀 무서울수도...)