druckt alle Primzahlzwillingspaar unter 100 in Python

Question

ein Programm schreiben, um zu bestimmen, wie viele Primzahlzwillingspaare gibt es unter 100

n = 100 # upper limit number 
k = range(3, int((n+1)**0.5) + 1, 2) 


def is_prime_pair(i, i2): 
if i <= 2 or i2 <= 2: 
    return False 
max_div = (i2 ** 0.5) + 1 
for x in k: 
    if (x > max_div or x == i or x == i2): 
     break 
    if (i % x == 0) or (i2 % x == 0): 
     return False 
return True 
for i in range(1, n+1, 2): 
    if is_prime_pair(i, i+2): 
     print "(" + str(i) + ", " + str(i+2) + ")" # Print pairs if prime pair 

Wie kann ich meinen Code zu optimieren, um es kürzer und schneller zu machen?

Answer 1

Erstellen Sie zuerst eine Liste der Primzahlen, die dann nach Zwillingen durchsucht werden. Auf diese Weise überprüfen Sie nie die gleiche Nummer zweimal als prime.

primes = [2] 
for candidate in xrange(3, 100, 2): 
    # Secondly don't try dividing potential primes by every odd number 
    # Just try dividing by the primes you already know! 
    for prime in primes: 
     if prime ** 2 > candidate: 
      primes.append(candidate) 
      break 
     if candidate % prime == 0: 
      break 

# Iterate through all positions in the list except the last to avoid an IndexError 
for i in xrange(len(primes) - 1): 
    if primes[i + 1] - primes[i] == 2: 
     print (primes[i], primes[i + 1]) 

Tupel sind so formatiert, wie Sie es möchten.

Answer 2

Wenn Sie wollen vor allem zu Ihrem aktuellen Code bleiben aber verbessern Details:

1. Verwenden for i in range(3, ..., da Sie wissen, dass ein gutes Paar nicht mit 1 oder 2 beginnen Dann können Sie if i <= 2... denn das wird entfernen nie passieren.
2. Es macht die Dinge schwieriger, eine is_prime_pair Funktion zu haben, die für die Primzahl von zwei Zahlen auf einmal prüft. Habe lieber eine is_prime Funktion, die eine einzelne Nummer testet und dann is_prime(i) and is_prime(i+2) aufruft.
3. Es ist klar, dass, wenn x nicht größer als max_div dann ist es weniger als i und i2 so or x == i or x == i2 entfernen. Übrigens braucht if (x > max_div or x == i or x == i2): diese zusätzlichen Klammern nicht: if x > max_div or x == i or x == i2: ist gültig.
4. Wenn x == max_div dann können Sie break bereits, weil max_div ist größer als die Quadratwurzel von x.
5. ** hat Vorrang vor + so zu max_div = i2 ** 0.5 + 1 vereinfachen.

So, jetzt haben wir:

def is_prime(i): 
    max_div = i ** 0.5 + 1 
    for x in k: 
     if x >= max_div: 
      break 
    ... 

Dies ist eine dumme Art und Weise ist, Dinge zu tun: iterieren nur einen Bereich, in dem max_div die obere Grenze ist! Sie müssen nur max_div in einen int konvertieren, um in der Bereichsfunktion erlaubt zu sein. Überzeugen Sie sich selbst, dass dies die richtige Sache ist, ob i ein perfektes Quadrat ist oder nicht und dass es keine Aus-von-Eins-Fehler gibt. Dann haben wir:

def is_prime(i): 
    max_div = int(i ** 0.5 + 1) 
    for x in range(3, max_div, 2): 
     if i % x == 0: 
      return False 
    return True 

Dies ist ein gemeinsames Muster, das bequem in Python Refactoring werden können:

def is_prime(i): 
    max_div = int(i ** 0.5 + 1) 
    return not any(i % x == 0 for x in range(3, max_div, 2)) 

(ich generator expression im Falle verwendet haben Sie damit nicht vertraut sind)

Sie können es mit zwei Tricks prägnanter machen, wenn auch möglicherweise schwerer zu lesen. Erste Inline max_div da es nur einmal verwendet wird.Dann statt any, können Sie all und behandeln Ints als booleans verwenden:

def is_prime(i): 
    return all(i % x for x in range(3, int(i ** 0.5 + 1), 2)) 

Hier wir sagen, dass eine Zahl prim ist, wenn es einige Nicht-Null-Rest verlässt, wenn sie von xfür alle x geteilt (daher die all Funktion) lohnt sich zu überprüfen. Dies funktioniert, weil in Python 0 wie False ist und alle anderen Zahlen wie True sind.

Wie in meiner anderen Antwort erwähnt, muss das Paar nicht manuell formatiert werden.

Da Sie print als eine Aussage verwendet haben, müssen Sie Python 2 verwenden, nicht 3, wie Ihr Tag sagt. In diesem Fall ersetzen Sie alle Instanzen von range durch xrange aus Effizienzgründen. es ist

Also am Ende nur:

n = 100 # upper limit number 

def is_prime(i): 
    return all(i % x for x in xrange(3, int(i ** 0.5 + 1), 2)) 

for i in xrange(3, n + 1, 2): 
    if is_prime(i) and is_prime(i + 2): 
     print (i, i + 2) 

jedoch zuversichtlich, dass ich bin, dass meine andere Antwort ist schneller, obwohl dies wahrscheinlich nicht nur für n = 100 zeigen. Das grellste Problem ist, dass, wenn immer i prim ist, dann is_prime(i + 2) aufgerufen wird und dann is_prime(i) in der nächsten Iteration der Schleife redundant ist, wie das gerade berechnet wurde. Sie können dies verbessern, indem Sie is_prime mit einem Set memoisieren.

Answer 3

Wie kann ich meinen Code optimieren, um ihn kürzer und schneller zu machen?

Hier Sieb-basierten Ansatz, der ein wenig kürzer und viel schneller ist:

def find_prime_pairs(n): 

    sieve = [True] * n 

    if n > 0: 
     sieve[0] = False 
     if n > 1: 
      sieve[1] = False 

    for number in range(2, int(n ** 0.5) + 1): 
     if sieve[number]: 
      for index in range(number * number, n, number): 
       sieve[index] = False 

    return [(a, b) for b, a in enumerate(range(0, n - 2), start=2) if sieve[a] and sieve[b]] 

print(*find_prime_pairs(100), sep='\n') 

USAGE

> python3 test.py 
(3, 5) 
(5, 7) 
(11, 13) 
(17, 19) 
(29, 31) 
(41, 43) 
(59, 61) 
(71, 73) 
> 

Wenn mit Primzahlen bis zu 100 arbeiten, wird jeder Code tun, es ist zu klein, um die Steuerperformance zu erreichen. Betrachten wir stattdessen 1000000 (eine Million). Aus Zeitgründen werden die Paare gezählt und nicht gedruckt.

Die erste Antwort von @AlexHall dauert doppelt so lang wie der ursprüngliche Code, um die Paare bis zu einer Million zu zählen. Seine zweite Antwort dauert dreimal länger als der ursprüngliche Code. Kürzere bedeutet nicht immer schneller. Traue keiner Antwort, bis du sie vollständig getestet hast.

Mein siebenter Code ist viermal schneller als der ursprüngliche Code und 15% kleiner.