[ Project Euler With Python ] 5. Smallest multiple

원문 : Smallest multiple

---

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible^[각주:1] by all of the numbers from 1 to 20?

2520 은 1 부터 10 까지의 숫자로 나눴을 때 나머지가 없이 나눠질 수 있는 가장 작은 숫자입니다.

1 부터 20 까지의 숫자들로 나눴을 때 나머지가 없이 나눠질 수 있는 가장 작은 숫자는 무엇일까요?

일단 특정 범위의 숫자로 나눴을 때 나머지가 없다는 이야기는 그 숫자들이 곱해져있다는 의미일 겁니다.

예를 들어 1 부터 10 까지의 숫자로 곱해진 숫자라면 어떤 수로 나눠도 나머지가 없는 수가 나오겠죠.

그런데 여기에서 우리는 규칙을 하나 알 수 있습니다. 합성수는 소수의 곱으로 되어 있기 때문에, 소수가 중복된다는 겁니다. 

예를 들어 10 은 2 * 5 로 구성되었기 때문에 2 와 5 가 중복됩니다. 그러면 2 와 5 를 한 번씩 빼도 2, 5, 10 으로 나누어 떨어질 수 있죠.

소인수 분해를 해 보도록 하겠습니다. 1 은 소수가 아니고 곱셈에 영향을 주지 않으므로 배제합니다.

여기에서 우리는 일련의 규칙을 발견할 수 있습니다. 소인수 분해를 했을 때 합성수를 만들기 위해서 필요한 최대 소수의 개수를 알 수 있다는 것입니다.

예를 들자면 4 로 나누기 위해서는 적어도 2 가 2 개가 존재해야 합니다. 6 으로 나누기 위해서는 적어도 2 가 1 개, 3 이 1 개가 존재해야 합니다. 8 로 나누기 위해서는 적어도 2 가 3 개가 존재해야 합니다. 9 로 나누기 위해서는 적어도 3 이 2 개는 존재해야 합니다. 10 으로 나누기 위해서는 적어도 2 가 1 개, 5 가 1 개가 존재해야 합니다. 그 이외의 소수들( 여기에서는 7 )은 1 개씩만 존재하면 되죠.

정리하면 2 가 3 개, 3 이 2 개, 5 가 1 개, 7 이 1 개가 필요합니다.

위의 문제와 동일한 답이 나오는군요.

Brute-Force

이제 알고리즘을 세워 보도록 하겠습니다.

• 2 부터 20 까지의 모든 수를 돌면서 소인수 분해를 합니다.
• 소인수 분해를 했을 때, 각 소인수의 개수를 세서, 소수의 최대 횟수를 구합니다.
• 소수의 최대 횟수만큼 곱합니다.

일단 소인수들을 구하는 함수는 [ 3. Largest prime factor ] 에서 가지고 왓습니다.

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 if 0 == ( i % 2 ) else 2 return prime_factors

이제 각 factor 의 카운트를 세서 곱하는 구현을 합니다.

total_max_count = dict() for i in range( 2, 21 ) : max_count = dict() prime_factors = get_prime_factors( i ) for p in prime_factors : if p in max_count : max_count[ p ] += 1 else : max_count[ p ] = 1 max_count_keys = max_count.keys() for key in max_count_keys : if key in total_max_count : total_max_count[ key ] = max( total_max_count[ key ], max_count[ key ] ) else : total_max_count[ key ] = max_count[ key ] smallest_number = 1 total_max_count_keys = total_max_count.keys() for key in total_max_count_keys : for c in range( total_max_count[ key ] ) : smallest_number *= key print( smallest_number )

조금 코드가 길지만 첫 번째 최상위 루프를 통해서 소인수들을 얻어서 최대 카운트를 셉니다. 그리고 두 번째 루프에서는 최대 카운트만큼 소인수들을 곱해줍니다.

결과는 232792560 입니다.

Other's solution

다른 해법이 있는지 찾아 봤습니다. 공식 PDF 에서는 뭔가 엄청 단순한 형태로 푸는군요. 뭔 sqrt 와 log 가 나오고 난리입니다. 기본적으로 반복횟수를 이용해서 푸는 것은 동일한데, 위의 식을 다음과 같이 표현하는데서 알고리즘을 시작합니다.

i 번째 소수를 pi 라고 하고 지수를 ai 라 할 때 N 은 다음과 같습니다.

여기에서 pi^ai 을 k 라고 하면, ai 는 다음과 같습니다.

예를 들어, k = 20 이라고 하면, 첫 번째 소수인 p1 = 2 입니다. 그러면 다음과 같이 a1 을 구할 수 있습니다.

정수여야 하므로 floor 를 사용합니다. 최적화를 위해서 pi <= sqrt( k ) 인 경우의 ai 만을 계산한다고 합니다.

이것을 일반화해서 다음과 같이 계산한다고 합니다.

자세한 건 pdf 에서 확인해 보시기 바랍니다.

1. divisible with no remainders [본문으로]