37. Truncatable primes

1. 개요

  문제는 이곳에서 확인할 수 있다. 3797은 재미있는 수인데, 그 자체로 소수일 뿐만 아니라 왼쪽 또는 오른쪽으로 한자리씩 지워나가도 모두 소수이다. 즉, 왼쪽으로 한자리씩 지워나갈 때 각각 379, 37, 3이 되는데 모두 소수이다. 마찬가지로 오른쪽으로 지워나갈 때 각각 797, 97, 7이되며 모두 소수이다. 이와 같은 특성을 지닌 소수를 truncatable prime이라고 하며 11개만 존재한다고 한다. truncatable prime의 합을 구하는 것이 목표이다. 단, 2, 3, 5, 7, 9는 truncatable prime가 아니다.

2. 구현 ver 1.0

에라스토테네스의 체를 사용하여 소수를 찾는다.

# -*- coding: utf-8 -*-
import math


class Prime:
    def __init__(self):
        self.is_prime = bytearray(2)
        self.make_more()

    def make_more(self):
        start = len(self.is_prime)
        end = start * 2

        self.is_prime += bytearray([1]) * (end - start + 1)

        for p in range(2, int(math.sqrt(end)) + 1):
            if self.is_prime[p]:
                m = end // p - p + 1
                self.is_prime[p * p::p] = bytearray(m)

    def truncate(self, p, direction):
        # direction: 0 for left to right, 1 for right to left

        p_str = str(p)
        len_str = int(math.log10(p))+1

        if direction == 0:
            for i in range(1, len_str):
                n = int(p_str[i:])
                if not self.is_prime[n]:
                    return False

        elif direction == 1:
            for i in range(1, len_str):
                n = int(p_str[:-i])
                if not self.is_prime[n]:
                    return False

        return True

count = 0
result = 0
prime = Prime()
prime_candidate = 11

while count != 11:

    while prime_candidate >= len(prime.is_prime):
        prime.make_more()

    if prime.is_prime[prime_candidate] and prime.truncate(prime_candidate, 0) and prime.truncate(prime_candidate, 1):
        count += 1
        print('{count}번째 수: {prime}'.format(count=count, prime=prime_candidate))
        result += prime_candidate

    prime_candidate += 2

print('RESULT: {result}'.format(result=result))

답은 748317이다.