[Project Euler] 47. Distinct primes factors, 48. Self powers

1. 47번 개요

  문제는 이곳에서 확인할 수 있다. 연속한 두개의 정수 중 두개의 서로 다른 소인수를 갖는 최초의 수는  $14=2\times 7$, $15=3\times 5$이다. 연속한 세개의 정수 중 세개의 서로 다른 소인수를 갖는 최초의 수는 $644=2^2\times 7\times 23$, $645=3\times 5\times 43$, $646=2\times 7\times 19$이다. 마찬가지로 연속한 네개의 정수 중 네개의 서로 다른소인수를 갖는 최초의 수에서 가장 처음 수를 구하는 것이 문제의 목표이다.

2. 47번 구현

  에라스토테네스의 체를 사용하여 소수를 구하고 그것을 사용하여 소인수분해를 하는 방법을 사용한다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

# -*- coding: utf-8 -*-   class Prime:          def __init__(self):         self.is_prime = bytearray([0])*2         self.prime_list = []         self.make_prime()       def make_prime(self):         temp_prime_list = []         self.is_prime += bytearray([1])*len(self.is_prime)         lim = len(self.is_prime)-1                  for p in range(0, lim):                          if self.is_prime[p]:                 temp_prime_list.append(p)                 m = lim//p - p + 1                 self.is_prime[p**2::p] = bytearray([0])*m           self.prime_list = list(set(self.prime_list) | set(temp_prime_list))         self.prime_list.sort()              def find_factor(self, n):                  while self.prime_list[-1] <= n:             self.make_prime()           factor = []         i = 0                  while n != 1:             p = self.prime_list[i]             temp_n, r = divmod(n, p)                          if r == 0:                 n = temp_n                 factor.append(p)             else:                 i += 1                  return set(factor)   p = Prime() i = 2 count = 0   while count != 4:     factor = p.find_factor(i)          if len(factor) == 4:         count += 1     else:         count = 0              i += 1      print(i-4)

  답은 134043이다. 하지만 문제가 하나 있는데, 속도가 너무 느리다는 것이다. 게시판에서 다른 사람들의 지혜를 엿보았는데 놀라운 내용이 많았다. 그 중 직관적으로 이해하기 쉬운 것을 소개한다.

  문제를 풀기 위해서 굳이 소인수분해를 할 필요는 없다. 왜냐하면 소인수만 찾으면 되기 때문이다. 에라스토테네스의 체를 약간 응용하면 소수를 미리 찾을 필요도 없다. 예를 들어 다음과 같은 숫자 쌍이 있다고 하자.

$$2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0,10:0$$

  2는 0의 값을 갖고 있는데, 이는 2가 소수라는 것을 의미한다. 2의 배수가 가진 값에 모두 1씩 더해준다. 그 다음 숫자인 3도 0의 값을 가지고 있으며 3의 배수가 가진 값에 모두 1씩 더해준다. 4는 1의 값을 가지고 있으므로 다음으로 0의 값을 가진 수를 만날 때까지 넘어간다. 이 과정을 모두 거치면 8은 1, 10은 2의 값을 갖게 되는데 이는 8의 소인수는 1개, 10은 2개라는 것을 의미한다. 놀라운 직관이다. 이를 아래와 같이 구현한다. 답도 정확하게 나오고 속도도 아주 빠르다.

?

1 2 3 4 5 6 7 8 9 10 11

# -*- coding: utf-8 -*-   lim = 1000000 n_factor = bytearray([0]) * lim   for i in range(2, int(lim**0.5)+1):     if not n_factor[i]:         for j in range(i, lim, i):             n_factor[j] += 1            print(''.join(map(str, n_factor)).index('4444'))

3. 48번 개요 및 구현

  문제는 이곳에서 확인할 수 있다. $1^1+2^2+\cdots +{1000}^{1000}$의 마지막 10자리를 구하는 것이 목표이다. python으로는 쉽게 구할 수 있다.

?

1 2 3 4

# -*- coding: utf-8 -*-   d = str(sum(n**n for n in range(1, 1001))) print(d[-11:-1])

  답은 9110846700이다.