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

Recommended Posts

Projet Euler 37
Projet Euler 7
Projet Euler 31
Projet Euler 4
Projet Euler 38
Projet Euler 17
Projet Euler 26
Projet Euler 8
Projet Euler 23
Projet Euler 22
Projet Euler 19
Projet Euler 50
Projet Euler 42
Projet Euler 33
Projet Euler 32
Projet Euler 43
Projet Euler 35
Projet Euler 36
Projet Euler 24
Projet Euler 46
Projet Euler 45
Projet Euler 6
Projet Euler 44
Projet Euler 39
Projet Euler 40
Projet Euler 49
Projet Euler 29
Projet Euler 41
Projet Euler 18
Projet Euler 13
Projet Euler 30
Projet Euler 16
Projet Euler 14
Projet Euler 34
Projet Euler 25
[Projet Euler] problème1
Projet Euler15 "Chemin du treillis"
Project Euler 2 Acceleration 2.21 Économisez des microsecondes.
Projet Euler Original Method Group 1
Qu'est-ce que Project Euler 3 Acceleration?
Programmation fonctionnelle dans Python Project Euler 1
Projet Euler 10 "Somme des nombres premiers"
Programmation fonctionnelle dans Python Project Euler 3
Projet Euler # 5 "Minimum Multiple" en Python
Projet Euler 4 Tentative d'accélération
Programmation fonctionnelle dans Python Project Euler 2
Projet Euler 11 "Produit maximum dans la grille"
Projet Euler # 15 "Lattice Path" en Python
Projet Euler # 4 "Calligraphie maximum" en Python
Projet Euler 9 Conservation des résultats des calculs
Projet Euler # 11 "Produit maximum dans la grille" en Python
Projet Euler # 7 "1000 1er nombre premier" en Python
Projet Euler # 9 "Numéro spécial Pitagolas" en Python
Projet Euler # 14 "Colonne de nombre de collats la plus longue" en Python
J'ai écrit Project Euler 1 en une seule ligne.
Projet Euler # 2 "Even Fibonacci Number" en Python
Projet Euler # 17 "Nombre de caractères" en Python
Projet Euler # 1 "Multiple de 3 et 5" en Python
Projet Euler # 8 "Produit maximum en chaîne numérique" en Python
Projet Euler # 10 "somme des nombres premiers" en Python
Projet Euler 28 Proposition de réponse inefficace Créer des "numéros en spirale"