schnell festzustellen, ob eine Zahl für Zahlen in Python prim <1 Milliarde

Question

ist Mein aktueller Algorithmus die Primalität von Zahlen in Python zu überprüfen Art und Weise für die Zahlen zwischen 10 Millionen und 1 Milliarde zu verlangsamen. Ich möchte, dass es verbessert wird, wissend, dass ich nie Zahlen größer als 1 Milliarde bekommen werde.

Der Kontext ist, dass ich nicht eine Implementierung bekommen kann, die schnell genug ist, um Problem 60 von Projekt Euler zu lösen: Ich bekomme die Antwort auf das Problem in 75 Sekunden, wo ich es in 60 Sekunden brauche. http://projecteuler.net/index.php?section=problems&id=60

Ich habe nur sehr wenige Speicher zu meiner Verfügung, so kann ich unter 1 Milliarde aller Primzahlen nicht speichern.

Ich verwende derzeit die Standard-Probedivision mit 6k ± 1 abgestimmt. Gibt es etwas besseres als das? Muss ich schon die Rabin-Miller-Methode für so große Zahlen bekommen?

primes_under_100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 
def isprime(n): 
    if n <= 100: 
     return n in primes_under_100 
    if n % 2 == 0 or n % 3 == 0: 
     return False 

    for f in range(5, int(n ** .5), 6): 
     if n % f == 0 or n % (f + 2) == 0: 
      return False 
    return True 

Wie kann ich diesen Algorithmus verbessern?

Präzision: Ich bin neu in Python und möchte mit Python arbeiten 3+ nur.

---

Schlusscode

Für diejenigen, die interessiert sind, MAK Ideen verwenden, erzeugen ich den folgenden Code, der etwa ein Drittel schneller ist, so dass ich das Ergebnis des euler Problems in weniger bekommen als 60 Sekunden!

from bisect import bisect_left 
# sqrt(1000000000) = 31622 
__primes = sieve(31622) 
def is_prime(n): 
    # if prime is already in the list, just pick it 
    if n <= 31622: 
     i = bisect_left(__primes, n) 
     return i != len(__primes) and __primes[i] == n 
    # Divide by each known prime 
    limit = int(n ** .5) 
    for p in __primes: 
     if p > limit: return True 
     if n % p == 0: return False 
    # fall back on trial division if n > 1 billion 
    for f in range(31627, limit, 6): # 31627 is the next prime 
     if n % f == 0 or n % (f + 4) == 0: 
      return False 
    return True 

Answer 1

Für Zahlen so groß wie 10^9 kann ein Ansatz sein, um alle Primzahlen bis zu erzeugen (10^9) sqrt und dann prüfen, einfach die Teilbarkeit der Eingangsnummer gegen die Zahlen in dieser Liste. Wenn eine Zahl nicht durch eine andere Primzahl kleiner oder gleich ihrer Quadratwurzel teilbar ist, muss sie selbst eine Primzahl sein (sie muss mindestens einen Faktor haben < = sqrt und ein anderes> = sqrt, um nicht prim zu sein). Beachten Sie, dass Sie die Teilbarkeit für alle Zahlen nicht testen müssen, nur bis zur Quadratwurzel (die etwa 32.000 ist - ziemlich überschaubar, denke ich). Sie können die Liste der Primzahlen mit einer sieve generieren.

Sie könnten auch für eine probabilistic prime test gehen. Aber sie können schwerer zu verstehen sein, und für dieses Problem sollte einfach eine generierte Liste von Primzahlen genügen.

Answer 2

können Sie zuerst teilen Sie Ihre n nur durch Ihre primes_under_100.

Auch vorberechnen mehr Primzahlen.

Auch speichern Sie Ihre range() Ergebnis im Speicher - verwenden Sie stattdessen irange() und verwenden Sie diesen Speicher für die Ausführung Sieve of Eratosthenes algorithm.

Answer 3

Für Projekt Euler Probleme zu lösen, ich habe getan, was Sie in Ihrer Frage vorschlagen: Umsetzung den Miller Rabin Test (in C#, aber ich vermute, dass es in Python schnell sein wird). Der Algorithmus ist nicht so schwierig. Für Zahlen unter 4.759.123.141 ist es ausreichend zu überprüfen, dass eine Zahl eine starke Pseudo-Primzahl für die Basen 2, 7, 61 ist. Kombinieren Sie diese mit der Versuchsteilung durch kleine Primzahlen.

Ich weiß nicht, wie viele der Probleme Sie bisher gelöst haben, aber einen schnellen Primzahltest zur Verfügung zu haben wird für viele Probleme von großem Wert sein.