Projet Euler 41

problème

Pan-numérique à N chiffres signifie que chaque chiffre a un nombre de 1 à n.

Différent de la définition mathématique comme indiqué dans le lien ci-dessous

Par exemple, 2143 est un nombre pan-numérique à 4 chiffres et est un nombre premier.N chiffres (9 chiffres ou moins dans la définition de ce problème) Répondez au plus grand nombre parmi les nombres premiers pan-numériques. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2041

Considération mathématique

Si la somme des nombres de chaque chiffre est un multiple de 3, le nombre lui-même sera un multiple de 3, mais pour 9 chiffres, 8 chiffres, 6 chiffres, 5 chiffres, 3 chiffres et 2 chiffres pan numérique, la somme de chaque chiffre est Puisqu'il s'agit d'un multiple de 3, il ne peut pas s'agir d'un nombre premier. Par conséquent, 7 chiffres et 4 chiffres doivent être vérifiés.

Répondre

Créez un numéro numérique panoramique à l'aide du générateur de nombres numériques panoramique que vous avez créé précédemment. Le fait qu'il s'agisse d'un nombre premier ou non est déterminé à partir d'un grand nombre numérique panoramique.

# 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)
    #Faire des multiples de 2 faux
    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()