Python - Projekt Euler # 35 - was ist los mit diesem Ansatz?

Question

Problem 35 von Project Euler ist wie so:

Die Zahl 197 ist eine kreisförmige prime, da alle Drehungen der Ziffern genannt: 197, 971 und 719, sie prim sind.

Es ist dreizehn solche Primzahlen unter 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79 und 97.

Wie viele kreisförmigen Primzahlen sind unter eine Million?

My, eher grob, ist Ansatz zunächst unter einer Million dann alle Primzahlen erzeugen alle Primzahlen auszufiltern, die auch Ziffern enthalten oder die Nummer 5 (wie es immer eine nicht-prime Permutation). Dann, für jedes Element in dieser reduzierten Liste von Primzahlen, um alle möglichen Permutationen der Zahl unter Verwendung der permutations() - Funktion in dem Iterool-Modul zurückzugeben, dann um zu überprüfen, ob irgendwelche dieser Permutationen nicht Primzahlen sind und wenn ja, um das Element zu entfernen die Liste der Primzahlen.

from itertools import permutations 

def gen_primes(limit): 
    D = {} 
    q = 2 
    while q <= limit: 
     if q not in D: 
      yield q 
      D[q * q] = [q] 
     else: 
      for p in D[q]: 
       D.setdefault(p + q, []).append(p) 
      del D[q]  
     q += 1 

def odd_primes(limit): 
    r = list(gen_primes(limit)) 
    for i in r[:]: 
     for j in str(i): 
      if any(int(j)%2 == 0 or int(j) == 5 for j in str(i)): 
       r.remove(i) 
       break 
    r.extend([2,5]) 
    return r  

def circular_list(): 
    prime_list = odd_primes(1000000) 
    for i in prime_list[:]: 
     perm = [''.join(j) for j in permutations(str(i))] 
     if any(int(j) not in prime_list for j in perm): 
      prime_list.remove(i) 
      break 
    return prime_list 

print len(circular_list) 

Die Ausgabe ergibt einen Wert, der mit einem gewissen Abstand falsch ist. Ich habe wirklich versucht, den Fehler in der Logik oder im Code (oder beiden) zu finden. Ist die Funktion permutations() ein praktikabler Ansatz?

Ich verstehe, dass es effizientere Ansätze gibt, aber ich wäre dankbar, wenn mir jemand in eine Richtung zeigen könnte, damit dieses funktioniert.

Answer 1

Das erste Problem ist, Sie brauchen Rotationen, nicht Permutationen. Eine Deque kann gedreht werden, damit wir sie ersetzen können. Das zweite Problem ist, dass odd_primes() eine Geschwindigkeitsoptimierung ist, die nicht hinzugefügt werden sollte, bis der grundlegende Code funktioniert, also werden wir es jetzt auslassen und haben circular_list() Anruf gen_primes() direkt. Natürlich ist ein primärer Generator nicht optimal, wie Sie herausgefunden haben, da wir zurück in die Liste der Primzahlen schauen müssen und ein Generator nur einmal durchlaufen werden kann.

Also hier ist, was hoffentlich funktioniert Code mit einem deque und sans odd_primes():

from collections import deque 

def gen_primes(limit): 
    D = {} 
    q = 2 
    while q <= limit: 
     if q not in D: 
      yield q 
      D[q * q] = [q] 
     else: 
      for p in D[q]: 
       D.setdefault(p + q, []).append(p) 
      del D[q]  
     q += 1 

def circular_list(limit): 
    circular = [] 

    primes = list(gen_primes(limit)) 

    for prime in primes: 
     string = str(prime) 
     digits = deque(string) 

     for rotation in range(1, len(string)): 
      digits.rotate(1) 

      if int("".join(digits)) not in primes: 
       break 
     else: 
      circular.append(prime) 

    return circular 

print(circular_list(1000000)) 

Welche Ausgänge:

[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199, 311, 337, 373, 719, 733, 919, 971, 991, 1193, 1931, 3119, 3779, 7793, 7937, 9311, 9377, 11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719, 93911, 99371, 193939, 199933, 319993, 331999, 391939, 393919, 919393, 933199, 939193, 939391, 993319, 999331] 

Wenn das gültige Ausgabe ist, jetzt gehen Sie zurück und schlüpfen in odd_primes() zu sehen, ob Es gibt Tricks, mit denen Sie die Geschwindigkeit optimieren können.

Answer 2

Mit dem großen Code von cdlane und Einführung der Geschwindigkeitsoptimierung auf der Grundlage, dass eine kreisförmige Strich mit mindestens zwei Ziffern nur aus Kombinationen der Ziffern 1, 3, 7 oder 9 bestehen kann, weil 0, 2, 4, 6 oder 8 als die letzte Ziffer der Zahl durch 2 teilbar ist, und mit 0 oder 5 als letzte Ziffer macht macht bekommen Sie es durch 5 teilbar (von https://en.wikipedia.org/wiki/Circular_prime):

from collections import deque 
import re 
import time 

def gen_primes(limit): 
    D = {} 
    q = 2 
    while q <= limit: 
     if q not in D: 
      yield q 
      D[q * q] = [q] 
     else: 
      for p in D[q]: 
       D.setdefault(p + q, []).append(p) 
      del D[q] 
     q += 1 

def exclude_primes(primes_list): 
    regex = re.compile("[024568]") 
    included_primes_list = [str(prime) for prime in primes_list if prime < 10 or regex.search(str(prime)) is None] 
    return included_primes_list 

def circular_list(limit): 
    circular_count = 0 

    primes = set(exclude_primes(gen_primes(limit))) 

    for prime in primes.copy(): # need copy to process allowing update original primes list 
     digits = deque(prime) 

     rotations = set() 
     for rotation in range(len(digits)): 
      digits.rotate(1) 
      rotations.add("".join(digits)) 
     # check all rotations at once 
     if rotations.issubset(primes): 
      circular_count += len(rotations) 
     # remove all rotations already checked from primes list 
     primes.difference_update(rotations) 

    return circular_count 

start_cpu_time = time.clock() 
print("Number of primes:", circular_list(1000000)) 
end_cpu_time = time.clock() 
print("CPU seconds:", end_cpu_time - start_cpu_time) 

Dies ist viel schneller als ohne die Optimierung, kann aber wahrscheinlich weiter optimiert werden.