[Project Euler] 49. Prime permutations

1. 개요

  문제는 이곳에서 확인할 수 있다. 1487, 4817, 8147은 3330씩 증가하는 수열인데 그 외에도 두가지 재미있는 특성이 있다. 첫번째는 각각이 모두 소수라는 점, 둘째는 각 숫자는 다른 숫자에서 배열을 바꿔 만들 수 있다는 점이다. 이와 같은 특성을 가진 4자리 숫자의 수열이 하나 더 존재한다. 그 수열을 연결한 12자리의 수를 찾는 것이 목표이다. 

2. 구현

  소수는 에라스토테네스의 체를 사용하여 구하며 숫자의 배열을 바꾸는 작업은 내장 모듈(itertools)를 사용한다. 

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

import itertools
import math

lim = 10000
is_prime = bytearray([1])*(lim+1)
is_prime[0] = is_prime[1] = 0

prime_list = []

for p, is_p in enumerate(is_prime):
	if is_p:
		m = lim//p-p+1
		is_prime[p**2::p] = bytearray([0])*m
		
		if int(math.log10(p)) == 3:
			prime_list.append(p)

answer = ''

while prime_list:
	
	p = prime_list[0]
	
	# Find permutation
	p_permu = map(lambda x: int(''.join(x)), itertools.permutations(str(p), 4))
	p_permu = list(set(filter(lambda x: x in prime_list, p_permu)))
	p_permu.sort()
	
	if not p_permu or len(p_permu) <= 2:
		prime_list.pop(0)
		continue
	
	prime_list = list(filter(lambda x: x not in p_permu, prime_list))
	
	# Check if the permutation fits the condition
	for numbers in list(itertools.combinations(p_permu, 3)):
		if numbers[2]-numbers[1] == numbers[1]-numbers[0]:
			print(numbers)
			answer = ''.join(map(str, numbers))
			
print('ANSWER: {a}'.format(a=answer))

답은 296962999629이다.