어떤 수를 소인수분해하면 그 수에 대한 소수로 이루어진 약수들을 얻을 수 있다. 예를 들어 13159에 대한 소수는 5, 7, 13, 29가 된다.

그렇다면 600851475143에 대한 소수 중 가장 큰 소수는 무엇인가?

풀이 #1

#!/usr/bin/env python3

MAX=600851475143 

prime_list = [2]
pf = []

def is_prime(n):
    if n == 2: return True
    for p in reversed(prime_list):
        if n % p == 0: return False
    return True

def prime_generator(m):
    for i in range(3, m, 2):
        if is_prime(i):
            yield i
            prime_list.append(i)

def prime_factorial():
    m = MAX
    for i in prime_generator(m//2):
        while True:
            if m % i == 0:
                pf.append(i)
                m = m // i
            else:
                break
        if m == 1: break

prime_factorial()
print(prime_list)
print(pf)

우선 소인수분해를 하기 위해서는 당연히 소수를 만들어낼 수 있어야 한다. 그래서 소수를 만드는 함수 prime_generator와 소수를 판별하는 함수 is_prime을 만들었다.

어떤 수가 소수가 되기 위해서는 1과 자기 자신으로만 나누어져야 하므로, 1부터 n/2까지의 수를 n에 나누어 보는 것으로 소수 여부를 판별할 수 있다. 나누는 것에 성공했다면 소수가 아니고 실패했다면 소수가 된다.

여기서 한번 더 최적화하면, 1부터 n/2까지의 수를 모두 나누어볼 필요가 없다. 왜냐 하면 소수가 아닌 모든 수들은 소수의 합성수로 볼 수 있기 때문이다. 예를 들어 4를 소인수분해하면 2와 2를 얻을 수 있는데, 어떤 수를 4로 나누는 것이 가능하다는 것은 4의 소수인 2로 나누는 것도 가능하다는 뜻이 된다.

소수를 매번 계산하지 않기 위해서 한번 계산된 소수는 prime_list에 저장한다. 이 소수 리스트는 is_prime에서 소수인지를 판별하기 위해 나누어볼 수로 사용한다. 따라서 많은 소수를 찾을수록 점점 더 많은 시간이 걸릴 것이다.