첫번째 문제로, 소수를 구해보는 함수를 만들어 보려고 합니다. 정수 N이 주어졌을 때, 그 N이 소수인지 아닌지를 return하는 함수를 만들어 보겠습니다.

가장 간단한 접근 방법은 2부터 차례로 올라가면서 N이 자기 자신을 제외하고 나누어 떨어지는 수가 있으면 N은 소수가 아니라고 할 수 있습니다. 그럼 이 방식을 적용해서 함수를 만들어 보겠습니다.

def isPrime1(N):
    if N < 2 :
        return False
    for i in range(2, N):
        if N % i == 0:
            return False #하나라도 나누어 떨어지는 것이 있다면 소수가 아닙니다.
    return True #만약 N-1까지도 안 나누어 떨어지면 N은 소수입니다.
import time
t0 = time.time()
print isPrime1(101)
print isPrime1(1000000)
print "걸린시간 : %.3e"%(time.time()-t0)
True
False
걸린시간 : 2.688e-02

함수가 잘 동작하는 것을 확인할 수 있죠? 그런데 중요한 것은 N이 커짐에 따라서 연산 속도가 급격히 느려진다는 점입니다. 코딩에 있어서 optimization은 필수라고 할 수 있는데요, 어떻게 하면 최적화를 할 수 있을까요?

def isPrime2(N):
    if N < 2:
        return False
    elif N == 2:
        return True
    elif N % 2 == 0:
        return False
    for i in range(3, N, 2):
        if N % i == 0:
            return False
    return True

isPrime2 함수는 결국 짝수들은 소수가 아니기 때문에 굳이 나눠볼 필요가 없다는 점을 착안해서 3부터의 홀수들만 가지고 N을 나눠보고 소수인지 아닌지 결정하는 함수입니다.

t0 = time.time()
print isPrime2(101)
print isPrime2(100000)
print "걸린시간 : %.3e"%(time.time()-t0)
True
False
걸린시간 : 1.150e-03

물론 N이 많이 커야 효과를 보겠지만, N=100,000만 되어도 거의 20배 가까이 차이가 나는 것을 확인할 수 있습니다. 어마어마한 차이가 되는거죠~ 연산을 1/2만큼 줄이는 효과가 있으니까요.

이보다 더 줄일 수는 없을까요?? 저도 최근에 깨우친 거지만, 이고, 결국 앞의 까지만 검사해본다면 후반부는 굳이 검사해 보지 않아도 전반부의 수들에 의해 다 필터가 될 것입니다. 다시 말해, 후반부에서 N을 나눌 수 있는 수가 존재한다면, 그 몫은 반드시 전반부에서 존재해야 하는 것을 이용하여 검사가 된다는 얘기입니다~

def isPrime3(N):
    if N < 2:
        return False
    elif N == 2:
        return True
    elif N % 2 == 0:
        return False
    for i in range(3, int(N**0.5)+1, 2): #여기서 +1을 해주는 것은 혹시나 버림하는 과정에서 에러가 발생할까봐 넣어준 것입니다.
        if N % i == 0:
            return False
    return True
t0 = time.time()
print isPrime3(101)
print isPrime3(100000)
print "걸린시간 : %.3e"%(time.time()-t0)
True
False
걸린시간 : 2.759e-04

또다시 엄청난 시간을 단축했죠?? 물론 더 단축할 방법들도 있겠지만, 이정도 하면 많이 묵은거 아닙니까?ㅎㅎㅎ 조그마한 알고리즘의 차이가 큰 결과로 이어진다는 소중한 교훈을 얻을 수 있었습니다 :-)