在隨機數字列表中獲得第一個素數

Question

我正在玩Python shell，我相信這是一個非常天真的函數實現，它只是返回100個隨機生成數字列表中的第一個素數（其值在0和99之間，包括在內）。下面的代碼：

>>> 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) 

我想這個函數返回嚴格只的第一素數。我的實現使用助手列表來緩存所有素數，然後簡單地返回第一個索引處的元素。它有效，但我不相信這是一個很好的。我確信有一個更有效的方法可以做到這一點，不需要掃描整個列表，但我似乎還沒有想到。

有什麼更好的選擇？

Answer 1

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

這種方式你不會一直搜索，一旦你發現一個主要。如果找不到素數，則函數隱式返回None。

Answer 2

是的，您甚至不需要生成所有隨機數字的列表，您可以在生成它們時測試每個隨機數字，並在找到它們後立即返回。

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

你說得對。你的代碼不僅具有更多的時間複雜性（即使在找到第一個素數之後仍然遍歷所有列表元素）和空間複雜度（用於保存所有素數的溫度列表），但是當代碼中沒有素數時，也可能會投擲IndexError名單。

所以，你可以修補它以下列方式：

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

注意，當有輸入的return聲明永遠不會得到執行，這意味着沒有明確的回報無素;在這種情況下Python返回None。因此，如果您選擇，您可以在for循環之外的函數結尾處返回您選擇的值，以指示「未找到」。

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

Pythonic處理這個問題的方法是引發異常並讓函數的調用者處理異常。

Answer 4

prime = next(filter(isprime, numbers)) 

參見find first element in a sequence that matches a predicate。