python 中的随机素数

Question

我目前将 ↓ 设置为我的 randprime(p,q) 功能。有什么方法可以通过 genexp 或 listcomp 之类的东西来压缩它？这是我的函数：

n = randint(p, q)
while not isPrime(n):
    n = randint(p, q)

Answer 1

最好只生成素数列表，然后从该行中进行选择。照原样，对于您的代码，如果区间中没有素数，或者如果 randint 总是选择非素数，则 while 循环将遇到无限循环的可能性很小永无止境。

所以这可能更短且麻烦更少：

import random
primes = [i for i in range(p,q) if isPrime(i)]
n = random.choice(primes)

这样做的另一个好处是，如果区间中没有素数，就不会出现死锁。如前所述，这可能会很慢，具体取决于范围，因此如果您提前缓存素数会更快：

# initialising primes
minPrime = 0
maxPrime = 1000
cached_primes = [i for i in range(minPrime,maxPrime) if isPrime(i)]

#elsewhere in the code
import random
n = random.choice([i for i in cached_primes if p<i<q])

同样，进一步的优化是可能的，但这在很大程度上取决于您的实际代码……而且您知道他们对过早优化的看法。

Answer 2

next(i for i in itertools.imap(lambda x: random.randint(p,q)|1,itertools.count()) if isPrime(i))

以 itertools.count() 开头 - 这给出了一个无限集合。

每个数字通过 itertools.imap() 映射到范围内的新随机数。 imap 类似于 map，但 returns 是一个迭代器，而不是一个列表 - 我们不想生成无限随机数的列表！

然后，找到第一个匹配的号码，并返回。

高效工作，即使 p 和 q 相距很远 - 例如1 和 10**30，无法生成完整列表！

顺便说一句，这并不比你上面的代码效率高，而且一眼看去更难理解——请考虑下一个程序员必须阅读你的代码，然后就去做就像你上面做的那样。六个月后，当你忘记这段代码应该做什么时，那个程序员可能就是你！

P.S - 在实践中，您可能希望将 count() 替换为 xrange（不是范围！），例如xrange((p-q)**1.5+20) 尝试的次数不超过该次数（在小范围和大范围的有限测试之间取得平衡，如果能够成功，失败的几率不超过 1/2%），否则，如建议的那样另一个 post，你可能会永远循环。

PPS - 改进：将 random.randint(p,q) 替换为 random.randint(p,q)|1 - 这使代码效率提高了一倍，但消除了结果为 2.

的可能性

Answer 3

因此，如果您可以使用迭代器以随机顺序（无需替换）给出从 p 到 q 的整数，那就太好了。我一直没能找到办法做到这一点。以下将给出该范围内的随机整数，并将跳过已经测试过的任何内容。

import random
fail = False
tested = set([])
n = random.randint(p,q)
while not isPrime(n):
    tested.add(n)
    if len(tested) == p-q+1:
        fail = True
        break
    while n in s:
        n = random.randint(p,q)

if fail:
    print 'I failed'
else:
    print n, ' is prime'

这样做的最大好处是，如果说您正在测试的范围只是 (14,15)，您的代码将永远运行。如果这样的素数存在，这段代码保证会产生一个答案，如果这样的素数不存在，则告诉你没有答案。你显然可以使它更紧凑，但我试图展示逻辑。

Answer 4

这是一个用 python 编写的脚本，用于在两个给定整数之间生成 n 个随机质数整数：


import numpy as np

def getRandomPrimeInteger(bounds):

    for i in range(bounds.__len__()-1):
        if bounds[i + 1] > bounds[i]:
            x = bounds[i] + np.random.randint(bounds[i+1]-bounds[i])
            if isPrime(x):
                return x

        else:
            if isPrime(bounds[i]):
                return bounds[i]

        if isPrime(bounds[i + 1]):
            return bounds[i + 1]

    newBounds = [0 for i in range(2*bounds.__len__() - 1)]
    newBounds[0] = bounds[0]
    for i in range(1, bounds.__len__()):
        newBounds[2*i-1] = int((bounds[i-1] + bounds[i])/2)
        newBounds[2*i] = bounds[i]

    return getRandomPrimeInteger(newBounds)

def isPrime(x):
    count = 0
    for i in range(int(x/2)):
        if x % (i+1) == 0:
            count = count+1
    return count == 1



#ex: get 50 random prime integers between 100 and 10000:
bounds = [100, 10000]
for i in range(50):
    x = getRandomPrimeInteger(bounds)
    print(x)

python 中的随机素数

Random prime Number in python

python

random

generator

list-comprehension

primes