[PYTHON] Project Euler 41

problem

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

Mathematical consideration

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.

Answer

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()