41. Pandigital prime

1. 개요

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

2. 구현

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

# -*- 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이다.