Erste Prime in einer Liste von Zufallszahlen

Question

Ich spielte mit der Python-Shell und ich habe, was ich glaube, eine extrem naive Implementierung einer Funktion, die einfach die erste Primzahl in einer Liste von 100 zufällig generierten Zahlen zurückgibt (deren Werte zwischen 0 und 99 liegen, inklusive). Code unten:

>>> def is_prime(n): 
    if n < 2: 
     return False 
    elif n == 2: 
     return True 
    for i in range(2, n): 
     if n % i == 0: 
      return False 
    return True 

>>> from random import randint 
>>> numbers = [] 
>>> for i in range(0, 100): 
    numbers.append(randint(0, 99)) 

>>> def get_first_prime(values): 
    temp = [] 
    for i in values: 
     if is_prime(i): 
      temp.append(i) 
    return temp[0] 

>>> get_first_prime(numbers) 

Ich möchte diese Funktion nur die erste Primzahl strikt zurück. Meine Implementierung verwendet eine Hilfsliste, um alle Primzahlen zwischenzuspeichern und dann das Element einfach an den ersten Index zurückzugeben. Es funktioniert, aber ich bin nicht davon überzeugt, dass es ein guter ist. Ich bin mir sicher, dass es einen effizienteren Weg gibt, dies zu tun, der nicht das Durchsuchen der gesamten Liste erfordert, aber ich kann noch nicht an einen denken.

Was sind bessere Alternativen?

Answer 1

def get_first_prime(values): 
    for i in values: 
     if is_prime(i): 
      return i 

Auf diese Weise Sie nicht weiter suchen, sobald Sie eine Primzahl finden. Die Funktion gibt implizit None zurück, wenn keine Primzahl gefunden wird.

Answer 2

Ja, Sie müssen nicht einmal eine Liste aller Zufallszahlen generieren, Sie können jede einzelne so wie sie erzeugt werden testen und zurückgeben, sobald Sie eine gefunden haben.

from random import randint 
import math 


def is_prime(n): 
    if n < 2: 
     return False 
    elif n == 2: 
     return True 
    for i in range(2, int(math.sqrt(n) + 1)): 
     if n % i == 0: 
      return False 
    return True 

def get_first_prime(number): 
    for i in range(number + 1): 
     n = randint(0, 99) 
     if is_prime(n): 
      return n 

get_first_prime(100) 

Answer 3

Sie haben Recht. Ihr Code hat nicht nur mehr Zeitkomplexität (indem er alle Listenelemente durchläuft, selbst nachdem er die erste Primzahl gefunden hat) und Raumkomplexität (temporäre Liste, um alle Primzahlen zu halten), sondern besteht auch die Gefahr IndexError zu werfen, wenn es keine Primzahlen gibt Liste.

So könnte man es auf die folgende Weise ausbessern:

def get_first_prime(values): 
    for i in values: 
     if is_prime(i): 
      return i 

Beachten Sie, dass, wenn es keine Primzahl in der Eingabe ist die return Anweisung nie ausgeführt werden sollen, das bedeutet, dass es keine explizite Rückkehr ist; In diesem Fall gibt Python None zurück. Wenn Sie also wählen, können Sie den Wert Ihrer Wahl am Ende der Funktion außerhalb von for zurückgeben, um "nicht gefunden" anzuzeigen.

Pythonic Art und Weise mit dies zu tun ist, eine Ausnahme auszulösen und den Anrufer der Funktion beschäftigen sich mit der Ausnahme.

Answer 4

prime = next(filter(isprime, numbers)) 

Siehe find first element in a sequence that matches a predicate.