N-digit pandigital means that each digit has a number from 1 to n.
Different from the mathematical definition as shown in the link below
For example, 2143 is a 4-digit Pandigital number and a prime number. N-digit (9 digits or less in the definition of this problem) Answer the largest number among Pandigital prime numbers. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2041
If the sum of the numbers of each digit is a multiple of 3, the number itself will be a multiple of 3, but for 9-digit, 8-digit, 6-digit, 5-digit, 3-digit, and 2-digit Pandigital, the sum of each digit is Since it is a multiple of 3, it cannot be a prime number. Therefore, 7 digits and 4 digits should be checked.
Create a Pandigital number using the Pandigital number generator you created earlier. Whether it is a prime number or not is determined from a large Pandigital number.
# coding: utf-8
# Here your code !
import copy
import math
def pandigital(digit,seq1,seq2=[]):
iter1 = map(str,seq1)
if seq2:
iter2 = map(str,seq2)
else:
iter2 = copy.deepcopy(iter1)
for d in range(digit-1):
iter1 = (x+y for x in iter1 for y in iter2 if not (y in x))
return iter1
def get_prime_boolean(max):
bool = [False,False]+[True]*(max-1)
#Multiples of 2 to False
bool[4::2] = [False] * (len(bool[4::2]))
p = 3
p_max = int(math.sqrt(max))+1
while p<=p_max:
if bool[p]:
bool[p**2::p] = [False] * (len(bool[p**2::p]))
p+=2
return bool
def get_prime_list(bool):
length = len(bool)
return [i for i in range(2,length) if bool[i]]
def get_primes(max):
bool = get_prime_boolean(max)
list = get_prime_list(bool)
return {'bool':bool,'list':list}
def is_prime(num,pri):
num = int(num)
if num < len(pri['bool']):
return pri['bool'][num]
M = (num**0.5)+1
#print num
for p in pri['list']:
if p > M:
return True
if (num % p) == 0:
return False
p = pri['list'][-1]+2
while p<M:
if (num % p) == 0:
return False
p += 2
return True
def main():
MAX=10**7
pri = get_primes(MAX)
ans = 0
for i in [7, 4]:
for pdg in pandigital(i,range(i,0,-1)):
if is_prime(pdg,pri):
ans = pdg
break
if ans:
break
print ans
main()
Recommended Posts