如何在NumPy中生成孪生素数？

wlzqhblo 于 2023-06-23 发布在其他

关注(0)|答案(2)|浏览(124)

我想使用NumPy生成twin primes。两个素数是孪生素数，如果它们的差是2。
我的想法很简单使用Eratosthenes的筛子生成素数，然后过滤掉不具有2差的相邻素数。
Erastothenes的Sieve代码实现是here。
这是我写的双素过滤器的实现：

import numpy as np

def twin_primes(n: int) -> np.ndarray:
   primes = prime_wheel_sieve(n)
   mask = np.isin(primes + 2, primes)
   mask |= np.concatenate([[False], mask])[:-1]
   return primes[mask]

预期输出应为：

In [367]: twin_primes(1000)
Out[367]:
array([  3,   5,   7,  11,  13,  17,  19,  29,  31,  41,  43,  59,  61,
        71,  73, 101, 103, 107, 109, 137, 139, 149, 151, 179, 181, 191,
       193, 197, 199, 227, 229, 239, 241, 269, 271, 281, 283, 311, 313,
       347, 349, 419, 421, 431, 433, 461, 463, 521, 523, 569, 571, 599,
       601, 617, 619, 641, 643, 659, 661, 809, 811, 821, 823, 827, 829,
       857, 859, 881, 883], dtype=int64)

我首先使用成员资格检查来查找素数，当增加2时，这些素数也是素数。这将找到所有孪生素数对中的第一个数字，但它将无法找到第二个数字。
这个问题可以归结为在True值之后立即翻转NumPy数组中的所有False值，因为在所有孪生素数对中，第二个数字必须是第一个数字之后的下一个素数。
我不确定如何在True之后翻转每个False，谷歌也没有帮助。因此，我将掩码右旋转1，以获得所有对中的第二个数字，并使用按位OR运算符组合两个掩码。
有没有更简单的方法来翻转True之后的所有False？
(as对于我之前的两个问题，我使用了AI建议的编辑）

numpy

来源：https://stackoverflow.com/questions/76497264/how-to-generate-twin-primes-in-numpy

2条答案

按热度按时间

ru9i0ody1#

如果你特别关心的是对np.isin的调用，你可以利用我们知道2不是孪生素数的事实，并执行以下操作：

def twin_primes_new(n: int) -> np.ndarray:
   primes = prime_wheel_sieve(n)
   mask = (primes-2)[1:] == primes[:-1]
   mask[:-1] |= mask[1:]
   return primes[1:][mask]

print(timeit.timeit('twin_primes_orig(1000)', globals=globals()))
print(timeit.timeit('twin_primes_new(1000)', globals=globals()))

我确实看到这对性能有了相当大的改进：

30.4948765
9.421712999999997

如果我们假设2不是孪生素数让你感到困扰，你可以在100万次执行中花费半秒的时间，做：

...
   mask = np.zeros(primes.shape, dtype=bool)
   mask[1:] = (primes-2)[1:] == primes[:-1]
   mask[:-1] |= mask[1:]
   return primes[mask]

赞(0）回复(0）举报 2023-06-23

bksxznpy2#

你的回答很好。另一种更直观的方法是太简单地取布尔数组的差并检查跳转发生的位置True -> False，这对应于-1的差（boolean：True！）。但是，如果+1（boolean：True）发生，我们不在乎，因为这意味着我们从False -> True开始，所以我们可以将元素设置为True。这导致以下简单表达式：

mask = np.isin(primes + 2, primes)
mask[np.diff(mask, prepend=False)] = True

PS：你包含了太多与你的问题无关的信息。你更有可能得到一个答案，如果你保持它的基本，在你的情况下：“如何在True条目之后翻转所有False条目？“.

赞(0）回复(0）举报 2023-06-23

我来回答

如何在NumPy中生成孪生素数？

2条答案

相关问题

热门标签

最新问答