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

我有一个填充随机数的列表，我想从此列表中返回素数。所以，我创建了这些功能：从Python中随机数列表过滤素数的最有效方法

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

但我想提高性能，所以我怎么能做到这一点？

来源

2017-07-02 flpn

这里有*吨的解决方案，特别是在SO上，显示了主要检查的实现。你有没有检查过他们？ – idjaw

不知道这是否有助于提高性能，因为我没有时间去测试任何东西，但是如果number> 1，则返回True，否则False可以归结为：return number> 1。 –

是的，有大量的素数检查解决方案，但它们都不适用于随机数列表的场景。 – flpn

Sieve of Eratosthenes，我的设备上以素数约0.17下秒千万上PyPy 3.5：

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

来源

2017-07-02 15:25:01 Ryan

一旦'我'达到'sqrt（上）''你已经确定了所有的素数。 – rici

这个筛子是否与随机数列表一起工作？ – flpn

@flpn：不，但是如果所有的随机数都是0-10,000,000，那么您可以获得该范围内的所有素数，并检查每个随机数是否在该组中。这就是'filter_primes = primes（10_000_000）.intersection' - 像往常一样调用'filter_primes（general_list）'。 – Ryan

这个怎么样？我认为这是一个好一点：

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

这种方式，我们不叫is_prime()为相同数量的多次。

来源

2017-07-02 14:54:46

Yeahhh，这有点帮助，谢谢！ – flpn

Eratosthenes的筛比试用部，你使用的方法更有效率。
您的审判部门循环可以变得更高效，花费大约一半的时间。两个是唯一的偶数，所以把两个视为一个特殊情况，之后只处理奇数，这会使工作减半。

我的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

这step 2在for循环是什么减半的工作。在先前已消除了所有甚至您只需使用奇试除数，以测试号码：3，5，7，...

来源

2017-07-02 15:15:32 rossum

这个筛子是否与随机数列表一起工作？ – flpn

这不是一个筛子，它只是测试提供的数字。如果你将它传递给相同的数字两次，它将测试该数字两次。一个筛子将计算每个数字的范围，并在询问时返回预先计算的结果。 – rossum

3轮的米勒罗宾测试（https://en.wikipedia.org/wiki/Miller%2dRabin_primality_test）使用碱2,7，以及61，是已知的准确检测所有素数< = 32位，即，任何适合python的东西。

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

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

来源

2017-07-02 16:50:31

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

回答

相关问题