从一个整数数组中过滤所有素数

Question

给定一个整数数组，如何返回一个包含所有素数的新数组？

def returnPrime (list):

示例：如下调用函数时：

returnPrime ((10,21,3,8,9,11,44,62,100,19))

它应该返回

[19,11,3]

Answer 1

def isPrime(n): 
if n <= 1: return False
for i in range(2, n): 
if n % i == 0: 
return False; 

return True
def returnPrime(list):
primes = []
for l in list:
for p in l:
if isPrime(p):
primes += p
return primes

如果你想要一个更快的版本，你必须用Eratosthenes筛生成素数并保存它们，那么检查将是O(1(。

Answer 2

import math
def return_primes(arr):
return list(filter(lambda x : is_prime(x), arr))
def is_prime(n):
for i in range(2, int(math.sqrt(n))):
if n % i == 0:
return False
return True
print(return_primes([10,21,3,8,9,11,44,62,100,19]))

Answer 3

您可以将isPrime((函数嵌入到prime过滤函数中：

def getPrimes(A):
def isPrime(N): return all(N%d for d in (2,*range(3,int(N**0.5)+1,2)))
return sorted(filter(isPrime,A),reverse=True)

输出：

r = getPrimes([10,21,3,8,9,11,44,62,100,19])
print(r)
# [19, 11, 3]

在大多数情况下，这比使用Eratosthenes的筛子要快。对于彼此相对接近的大型数字列表(例如[100+i*7+2 for i in range(100)](，"筛子"确实提供了更好的性能。

这里有一个函数的例子，如果你想玩Eratosthenes筛并看看它的区别：

def getPrimes2(A):
maxA = max(A)
isPrime = [False]*2+[True]*(maxA-1)        # sieve bits covering A
for n in (2,*range(3,maxA+1,2)):           # run through divisors
if not isPrime[n]: continue
isPrime[n*n::n] = [False]*len(isPrime[n*n::n]) # flag non-primes
primes = [a for a in A if isPrime[a]]      # filter A on primes
return sorted(primes,reverse=True)         # return sorted result

如果您知道列表可以包含的最大值，并且函数将被多次调用，则可以通过在全局变量中提前准备isPrime列表来提高整体性能。如果排除设置isPrime列表所需的时间，则每次调用getPrimes((的性能将快几个数量级：

maxPrime = 1000000                             # largest number in lists
isPrime = [False]*2+[True]*(maxPrime-1)        # sieve bits covering A
for n in (2,*range(3,maxPrime+1,2)):           # run through divisors
if not isPrime[n]: continue
isPrime[n*n::n] = [False]*len(isPrime[n*n::n]) # flag non-primes
def getPrimes(A):
return sorted((a for a in A if isPrime[a]),reverse=True)