[PYTHON] Projekt Euler 41

Problem

N-stellig pan-digital bedeutet, dass jede Ziffer eine Zahl von 1 bis n hat.

Abweichend von der mathematischen Definition, wie im folgenden Link gezeigt

Zum Beispiel ist 2143 eine 4-stellige pan-digitale Zahl und eine Primzahl. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2041

Mathematische Überlegung

Wenn die Summe der Zahlen jeder Ziffer ein Vielfaches von 3 ist, ist die Zahl selbst ein Vielfaches von 3, aber für 9-stellige, 8-stellige, 6-stellige, 5-stellige, 3-stellige und 2-stellige Pan-Digital ist die Summe jeder Ziffer Da es ein Vielfaches von 3 ist, kann es keine Primzahl sein. Daher sollten 7 Ziffern und 4 Ziffern überprüft werden.

Antworten

Erstellen Sie eine Pan-Digital-Nummer mit dem zuvor erstellten Pan-Digital-Nummerngenerator. Ob es sich um eine Primzahl handelt oder nicht, wird anhand einer großen digitalen Schwenkzahl bestimmt.

# 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)
    #Machen Sie ein Vielfaches von 2 Falsch
    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()