[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번 구현

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

# -*- 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, \quad 3:0, \quad 4:0, \quad 5:0, \quad 6:0, \quad 7:0, \quad 8:0, \quad 9:0, \quad 10:0$$

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

# -*- 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으로는 쉽게 구할 수 있다.

# -*- coding: utf-8 -*-

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

  답은 9110846700이다.