从 numpy 数组中获取素数

Question

我有一个像这样的 numpy 数组，

 nums = np.array([17, 18, 19, 20, 21, 22, 23])

如何以 pythonic 方式从这个数组中过滤掉素数？我知道要做一个简单的过滤，比如，

 nums[nums > 20]   #array([21, 22, 23])

有没有办法传递 lambda 函数进行过滤？

预期输出：array([17, 19, 23])

原文由 user6084800 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

我这样做的方式是使用 gmpy 或开发了良好素性测试算法的第 3 方库。 Miller-Rabin 素数测试通常是一个非常安全（而且快速！）的选择。如果你只是想要慢的方式，你可以这样做：

 import numpy as np
import math

def is_prime(n):
    if n % 2 == 0 and n > 2:
        return False
    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))

a = np.arange(1, 10**3)
foo = np.vectorize(is_prime)
pbools = foo(a)
primes = np.extract(pbools, a)
primes  # => Output below
array([  1,   2,   3,   5,   7,  11,  13,  17,  19,  23,  29,  31,  37,
        41,  43,  47,  53,  59,  61,  67,  71,  73,  79,  83,  89,  97,
       101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
       167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
       239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311,
       313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389,
       397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
       467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563,
       569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
       643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727,
       733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821,
       823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907,
       911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997])

如果你想过滤掉素数，只需在 pbools 变量上调用 np.invert 。任何谓词也是如此。您还可以将 lambda 传递给矢量化。例如，假设我们只想要与 5 相差 1 的质数（无论出于何种原因）。

 import numpy as np
import math

def is_prime(n):
    if n % 2 == 0 and n > 2:
        return False
    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))

a = np.arange(1, 10**3)
foo = np.vectorize(lambda x: (not (x + 1) % 5 or not (x - 1) % 5) and is_prime(x))
primes = a[foo(a)]  # => Shorthand.... Output below
array([  1,  11,  19,  29,  31,  41,  59,  61,  71,  79,  89, 101, 109,
   131, 139, 149, 151, 179, 181, 191, 199, 211, 229, 239, 241, 251,
   269, 271, 281, 311, 331, 349, 359, 379, 389, 401, 409, 419, 421,
   431, 439, 449, 461, 479, 491, 499, 509, 521, 541, 569, 571, 599,
   601, 619, 631, 641, 659, 661, 691, 701, 709, 719, 739, 751, 761,
   769, 809, 811, 821, 829, 839, 859, 881, 911, 919, 929, 941, 971, 991])

原文由 Goodies 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

如果您关心速度和效率，我建议您使用 最快的素筛 之一和 numpy.intersect1d() 函数：

 import numpy as np

def primesfrom2to(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Input n>=6, Returns a array of primes, 2 <= p < n """
    sieve = np.ones(n//3 + (n%6==2), dtype=np.bool)
    sieve[0] = False
    for i in range(int(n**0.5)//3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      ((k*k)//3)      ::2*k] = False
            sieve[(k*k+4*k-2*k*(i&1))//3::2*k] = False
    return np.r_[2,3,((3*np.nonzero(sieve)[0]+1)|1)]

# generate 100.000 random integers from 1 to 1.000.000.000
a1 = np.random.randint(1, 10**9, 100000)
# generate all primes that are equal or less than a1.max()
primes = primesfrom2to(a1.max())

# print result
print(np.intersect1d(primes, a1))

原文由 MaxU - stop russian terror 发布，翻译遵循 CC BY-SA 4.0 许可协议