获取随机数列表中的第一个素数

Question

我在玩 Python shell 我认为这是一个非常天真的函数实现，它只是 return 列表中的第一个素数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)

我希望这个函数严格return只第一个质数。我的实现使用帮助列表来缓存所有素数，然后简单地 return 第一个索引处的元素。它有效，但我不相信它是一个好东西。我确信有一种更有效的方法不需要扫描整个列表，但我似乎还想不出一个。

有哪些更好的选择？

Answer 1

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

这样你就不会在找到质数后继续搜索。如果未找到素数，则函数隐式 returns None。

Answer 2

是的，您甚至不需要生成所有随机数的列表，您可以在生成每个随机数时对其进行测试，一旦找到一个就return。

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

你是对的。您的代码不仅具有更多的时间复杂度（运行即使在找到第一个素数之后也会遍历所有列表元素）和 space 复杂度（临时列表包含所有素数）而且还有抛出 IndexError 当列表中没有质数时。

所以您可以通过以下方式修复它：

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

请注意，当输入中没有素数时，return 语句将永远不会执行，这意味着没有明确的 return；在这种情况下 Python returns None。因此，如果您选择，您可以 return 在 for 循环外的函数末尾选择您选择的值来指示 'not found'.

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

Python处理这个问题的 ic 方法是引发异常并让函数的调用者处理异常。

Answer 4

prime = next(filter(isprime, numbers))

参见find first element in a sequence that matches a predicate。

获取随机数列表中的第一个素数

Getting First Prime in a List of Random Numbers

python

primes

python-3.x