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

Question

我有一个充满随机数的列表，我想从这个列表中 return 素数。所以我创建了这些函数：

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

这个怎么样？我觉得好一点:

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

这样我们就不会多次为同一个号码调用 is_prime()。

Answer 2

Eratosthenes 筛法比 Trial Division 更有效，您正在使用的方法。
您的试验除法循环可以变得更有效率，花费大约一半的时间。 2是唯一的偶素数，所以把2当作特例，以后只处理奇数，这样工作量会减半

我的 Python 是不存在的，但是这个伪代码应该清楚：

def isPrime(num)

  // Low numbers.
  if (num <= 1)
    return false
  end if

  // Even numbers
  if (num % 2 == 0)
    return (num == 2)  // 2 is the only even prime.
  end if

  // Odd numbers
  for (i = 3 to sqrt(num) + 1 step 2)
    if (num % i == 0)
      return false
    end if
  end for

  // If we reach here, num is prime.
  return true;

end def

for 循环中的 step 2 将工作减半。之前消除了所有偶数后，您只需要使用奇数试验除数进行测试：3、5、7，...

Answer 3

Sieve of 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

Answer 4

3 轮 Miller-Rabin 测试 ( https://en.wikipedia.org/wiki/Miller%2dRabin_primality_test ) 使用基数 2、7 和 61，已知可以准确检测所有 <= 32 位的素数，即任何符合 python int.

如果数字很大，这比试验除法或筛选要快得多。

如果数字不能很大（即 < 10,000,000，正如您在评论中建议的那样），那么您可能需要预先计算所有素数 < 10,000,000 的集合，但其中有超过 600,000 个。

Answer 5

def primes_list(num_list):
    divs = [2,3,5,7]
    primes = [x for x in set(num_list) if 0 not in {1 if ((x%i != 0) | (x in divs)) & (x > 0) else 0 for i in divs}]
    return primes

对于此函数，它需要一个列表 num_list 作为参数。 divs 是一个预定义的，或者更确切地说是硬编码的，小于 10（不包括 1）的素数列表。然后我们使用列表理解来过滤 num_list 作为变量 primes 的素数。

Answer 6

这是另一种用于查找范围素数的代码。简单易行的方法。

    def find_prime(n):
       if n <=1:
         return False
       else:
          for i in range(2, n):
              if n % i == 0:
                  return False
       return True
n = 10
x = filter(find_prime, range(n)) #you can give random no list too
print(list(x))

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

Most efficient way to filter prime numbers from a list of random numbers in Python

python

algorithm

performance

primes

python-3.x