41. Pandigital prime

1. 개요

  문제는 이곳에서 확인할 수 있다. 어떤 수의 각 자리수가 1부터 $n$까지의 정수가 한번만 등장할 때 이 숫자를 $n$ pandigital이라고 한다. 예를 들어 2143은 4 pandigital인데 소수이기도 하다. 이와 같이 pandigital이면서 소수인 $n$ panditial 중 가장 큰 수를 구하는 것이 문제의 목표이다.

2. 구현

  $n$ pandigital의 정의상 확인해야 할 가장 큰 수는 987654321이다. 그런데 9 pandigital과 8 pandigital 각각은 그 자리 수의 합이 3의 배수이기 때문에 소수가 아니다. 따라서 7654321부터 문제의 조건을 확인하면 된다. 이를 이용하여 구현한다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

# -*- coding: utf-8 -*-   import math   max_int = 7654321 # for 7654321   is_prime = bytearray([1]) * (max_int + 1) is_prime[0] = is_prime[1] = 0   for p in range(2, int(math.sqrt(max_int))+1):           if is_prime[p]:         m = max_int // p - p + 1         is_prime[p*p::p] = bytearray([0])*m   for p in range(max_int, 0, -1):     if is_prime[p]:         set_p = str(p)         if set([int(s) for s in set_p]) == set(range(1,len(set_p)+1)):             print('ANSWER: {p}'.format(p=p))             break

답은 7652413이다.