그냥 그런 블로그

원문 : Largest prime factor

Prime factor

일단 소인수가 뭔지 알아야 합니다. 일단 제가 알고 있는있는 소인수의 정의는 다음과 같습니다.

자신과 1 을 제외하고는 나눠지지 않는 않는 수.

실제 정의를 찾아 보았습니다만, 위에서 제가 한 정의는 "소수( prime number )" 에 대한 정의군요. 그리고 자연수여야 한다는 조건도 빠졌구요.

소수(素數, 발음: [소쑤], 문화어: 씨수, 영어: prime number)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. ( 중략 ) 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다.

출처 : [ 1 ].

구글 사전에서는 소인수를 다음과 같이 정의하더군요.

어떤 정수(整數)를 소수(素數)만의 곱으로 나타낸 때의 각 인수(因數).

구글 사전에서는 인수를 다음과 같이 정의하고 있습니다.

정수 또는 정식(整式)을 몇 개의 곱의 형태로 하였을 때, 그것의 각 구성 요소. 인자(因子).

즉 소인수는 "소수인 인수" 를 의미하는 거군요.

Generate prime numbers

그럼 가장 먼저 생각해 봐야 할 부분은 소수를 검사할 수 있는 방법이겠네요. 일단 소수값들을 나열해 봤습니다.

2 가 유일한 짝수이고 나머지는 홀수입니다. 그렇다면 계산의 시작은 더 이상 2 로 나눠질 수 없을 때까지 2 로 나누는 거겠죠.

예를 들어 60 이라는 수는 2 * 2 * 15 로 구성됩니다. 그러면 15 라는 수가 남네요. 이제 다음 소수인 3 으로 같은 작업을 반복할 수 있을 것입니다. 그러면 15 는 3 * 5 로 구성됩니다. 그러면 5 라는 수가 남네요. 이제 다음 소수인 5 로 같은 작업을 수행합니다. 그러면 5 * 1 이 되고, 1 은 나눌 수 없으니 계산이 종료될 겁니다. 결국 2, 3, 5 가 60 을 구성하는 소인수들이 됩니다. 

그런데 이건 합성수의 소인수를 찾는 것( 소인수분해 )이지 소수 자체를 구하는 것이 아닙니다. 그런데 이 소인수분해를 하는 과정자체가 소수를 찾는 과정이 아닐까라는 생각이 들었습니다.

왜냐하면 "자신과 1 을 제외한 자연수로 나눌 수 없는 자연수" 라는 정의를 생각하면 다음과 같은 가정을 깔 수 있을 것이기 때문입니다.

자신보다 작은 소수로 나눠봤을 때 나누어 떨어지면 그것은 소수가 아니다.

그러면 아래와 같이 소수를 생성해 볼 수 있습니다.

prime_numbers = [ 2 ] def generate_prime_numbers( max ) : for i in range( 3, max + 1) : is_prime_number = True for p in prime_numbers : if 0 == ( i % p ) : is_prime_number = False break if is_prime_number : prime_numbers.append( i ) generate_prime_numbers( 100 ) print( prime_numbers )

대충 살펴 보니 맞는 것 같군요.

그런데 여기에서 우리가 목표로 하는 600,851,475,143 을 넣고 generate_prime_factors() 를 호출하면 상상도 못할 시간이 걸리게 됩니다. 아무리 기다려도 끝날 생각을 하지 않습니다.

왜냐하면 이것의 시간복잡도는 O( i * p ) 이기 때문입니다; 여기에서 i 는 max 이고 p 는 i 보다 작은 소수의 개수입니다. 그러므로 최악의 경우라도 O( i^2 ) 보다는 작습니다만 max 가 워낙 크기 때문에 답이 없습니다.

그러므로 이건 적어도 이 문제를 풀기 위해서는 사용할 수 없는 함수입니다. 물론 언젠가는 계산이 끝나기는 하겠죠.

최적화를 위해서 병렬화를 고민해 볼 수도 있겠지만, 그건 너무 나간 것 같구요, 알고리즘적으로 해결할 수 있는 방법을 찾아 봐야 합니다.

Optimization : Only odd numbers

일단 단순하게 생각했을 때 2 의 배수인 숫자들( 즉, 짝수 )를 배제하면 대상이 절반이 줄어듭니다.

3 에서 시작한 것이니 for 문의 증가값을 2 로 하면 홀수만 나오게 되죠.

for i in range( 3, max + 1, 2 ) :

Optimization : Reduction

하지만 여전히 검사해야 할 숫자의 개수가 많습니다. 그런데 더 생각나는 방법은 없더군요. 그래서 참고자료를 찾아 봤습니다. [ 1 ] 에서는 다음과 같이 언급하고 있더군요.

그렇군요. 대상을 아예 없애 버리면 됩니다. 하지만 두 가지 문제가 있습니다.

• 메모리 문제 : 메모리가 버텨 줄 것인가?
• list operation : append, remove 등의 연산의 비용은 어떻게 할 것인가?

일단 메모리 문제를 검증해 봤습니다. 2 의 배수만을 배제한다고 가정했을 때, 배열의 크기는 1 GB 정도입니다. 5 의 배수까지 배제한다면 더 줄어들 수 있겠죠. 이 정도는 크게 문제가 없을 것이라는 판단을 했습니다.

두 번째로 list 관리 문제인데요, 소수가 아닌 것들에는 -1 값을 넣어 두면 되기 때문에 별 문제는 없을 것으로 보입니다. 게다가 저는 대상을 배제하는 기법을 사용하는 것이 아니라 소수인지 여부를 검사하는 기법을 사용하고자 합니다. 왜냐하면 대상을 배제하는 기법은 자신보다 큰 값들에 대해서 루프를 검사하는 비용이 들기 때문입니다. 결국에는 소수의 루프를 돌면서 검사하는 것과 크게 다르지 않은 비용이 나올 것이라고 생각합니다. 둘다 이중 루프로 시간복잡도는 거의 동일하기 때문입니다.

def generate_prime_numbers( max ) : prime_numbers = [ 2 ] # gather target numbers except multiples of 2 or 5 targets = list() for i in range( 3, max + 1, 2 ) : if 1 == ( i % 5 ) : targets.append( i ) # check if each item is not a prime number for i in targets : is_prime_number = True for p in prime_numbers : if 0 == ( i % p ) : is_prime_number = False break if is_prime_number : prime_numbers.append( int( i ) ) # return result. return prime_numbers

꽤 많이 배제한 상태임에도 불구하고, i7-4770K 에서 2 분이 지나도록 끝이 안 나더군요. 이것이 list 의 append() 에 드는 비용이 아닌가라는 의심이 들기 시작했습니다. 찾아 보니까, [ 간단한 구문 변경으로 속도를 향상시키기 ] 에서 백만개를 돌리는데 109 ms 를 소비하더군요. 물론 2015 년 자료니 머신의 성능이 어떤지는 모르겠지만, 시간이 많이 걸리는 건 사실입니다. 우리의 목표는 6000 억개이기 때문에 홀수만 따져도 3000 억개입니다. 단순하게 산술계산을 하면 60 만배이고 1000 ms 가 1 초이므로, 6 만초( 16.6 시간 )가 걸립니다. 그러므로 절대 append() 를 많이 사용해서는 안 되는 상황인 것입니다.

링크의 문서에 나온 것처럼 루프 밖에서 append 함수를 미리 선언하는 방식을 사용해 봤습니다( 마치 함수 포인터같은 녀석입니다 ).

target_append = targets.append for i in range( 3, max + 1, 2 ) : if 1 == ( i % 5 ) : target_append( i )

비용이 30 % 정도 줄어든다고 하니 기대시간은 약 11.62 시간입니다. 이것도 용납할 수 없는 수치입니다.

이걸 빠르게 할 수 있는 방법이 있으면 누군가 공유해 줬으면 좋겠군요.

추가 : [ 7. 10001st Euler ] 를 풀면서, 2 의 배수, 5 의 배수를 배제하고 소수를 뽑아 봤는데, 예상한 것과는 다르게 1 ~ 2 분 정도밖에 안 걸리더군요. 그러므로 위에서 예측한 비용은 잘못된 것으로 보입니다.

Prime Factorization

뭐 굳이 소수의 리스트가 없어도 문제를 해결할 방법은 있습니다.

원래 값을 2 부터 시작해서 나눕니다. 그리고 나머지가 0 이 아니면 다음 숫자로 넘어 갑니다. 나머지를 0 으로 만드는 수는 소인수라 생각할 수 있습니다.

def get_prime_factors( target ) : quotient = target prime_factors = list() append_factors = prime_factors.append i = 2 while( 1 != quotient ) : remainder = quotient % i if 0 == remainder : quotient /= i append_factors( i ) else : i += 1 return prime_factors prime_factors = get_prime_factors( 600851475143 ) print( prime_factors ) print( prime_factors[ len( prime_factors ) -1 ] )

답은 6857 입니다.

다른 사람들은 어떻게 풀었는지 확인해 봤는데 별 차이는 없네요. 단지 MathBlog 에서는 0 ms 에 가까운 대안을 소개하고 있습니다( 앞에서 소개했던 짝수배제 기법입니다 ). 

근데 컴퓨터가 좋아서인지 최적화를 안 해도 저는 0.0107 ms 가 나오는군요. 어쨌든 빠르면 좋은거니 저도 홀수를 배제해 봤습니다. 

i += 1 if 0 == ( i % 2 ) else 2

그랬더니 0.0058 ms 로 반쯤 줄어드는군요. 여기에서 5 의 배수도 배제해 봤습니다.

next = i + 1 i += 2 if ( 0 == ( next % 2 ) ) or ( 0 == ( next % 5 ) ) else 1

그런데 조건문이 두 개가 되지 비용만 더 올라갑니다( 0.0068 ms ). 너무 작은 비용에 대한 부적절한 최적화는 오히려 해가 된다는 사실을 알게 되네요.

전체 소인수 리스트를 수집하기 위해서 append() 를 사용하고 있습니다. 이를 배제하고 마지막 소인수만 반환한다면 더 빠른 결과를 볼 수 있습니다( 0.0048 ms ). 하지만 기본 while 비용이 있으므로 여기에서 드라마틱하게 내려가지는 않네요.

def get_last_prime_factor( target ) : quotient = target last_prime_factor = -1 i = 2 while( 1 != quotient ) : remainder = quotient % i if 0 == remainder : quotient /= i last_prime_factor = i else : i += 1 if 0 == ( i % 2 ) else 2 return last_prime_factor

참고자료

[ 1 ] 소수 ( 수론 ), 위키피디아.

[ 2 ] 소인수분해, 위키피디아.