从Python中的随机数列表中过滤素数的最有效方法

Question

我有一个填充随机数的列表,我想从此列表中返回素数.所以我创建了这些函数:

def is_prime(number):
    for i in range(2, int(sqrt(number)) + 1):
        if number % i == 0:
            return False

    return number > 1

和

def filter_primes(general_list):
    return set(filter(is_prime, general_list))

但我想提高性能,那么我该如何实现呢？

Answer 1

在Eratosthenes筛选,在我的设备上使用PyPy 3.5的1000万以下的素数大约需要0.17秒:

from array import array

def primes(upper):
    numbers = array('B', [1]) * (upper + 1)

    for i in range(2, int(upper ** 0.5) + 1):
        if numbers[i]:
            low_multiple = i * i
            numbers[low_multiple:upper + 1:i] = array('B', [0]) * ((upper - low_multiple) // i + 1)

    return {i for i, x in enumerate(numbers) if i >= 2 and x}

和过滤功能:

filter_primes = primes(10_000_000).intersection