在给定范围内创建仅一个随机质数

Question

我希望您可以在给定的任何范围内创建唯一的随机质数。 我有以下代码：

print [x for x in range(5000, 5200)
  if not [t for t in range(2, x)
    if not x % t]]

但是我的程序提供了一组质数。我想修改我的代码，仅在任何给定范围内创建一个随机数，但我找不到如何实现。 请帮助。

- Nafi Shahriyar

---

请注意，并非每个范围都包含质数。但是，例如，在“n”和“2*n”之间总会有一个质数。 - hilberts_drinking_problem

Answer 1

方法一：

import random
random.choice([x for x in range(5000, 5200) if not [t for t in range(2, x) if not x % t]])

实际上你已经接近成功了，你只需要使用random.choice()函数即可。

---

方法二：

或者你也可以使用permutation函数来随机排列素数范围，然后选择第一个元素：

import numpy as np
np.random.permutation([x for x in range(5000, 5200) if not [t for t in range(2, x) if not x % t]])[0]

- MaThMaX

---

这个程序无法运行。编译器报错：“没有找到 random 模块”。我写的跟你的一模一样。 - Nafi Shahriyar

random 是一个内置模块，必须导入才能使用。 - SvbZ3r0

@Rasel，你有导入random吗？ - MaThMaX

是的，我做了。我按照你的方式写的。 - Nafi Shahriyar

@Rasel，这很奇怪，因为正如Gughan Ravikumar所说，它是Python2和Python3的内置包。 - MaThMaX

Answer 2

我对mathmax的解决方案的问题是，它在寻找5000到5200之间的质数时做了所有的工作，只选择其中一个并放弃其余部分。可能更有效的方法是随机选择5000到5200之间的唯一数字，直到找到第一个质数：

import random

minimum = 5000
maximum = 5200

next((x for x in random.sample(range(minimum, maximum), maximum - minimum) if not [t for t in range(2, x) if not x % t]), None)

这是快了大约18倍。如果我们在素数测试方面再聪明一些，可以再获得18倍的改进：

next((x for x in random.sample(range(minimum, maximum), maximum - minimum) if not [t for t in [2] + list(range(3, int(x**0.5) + 1, 2)) if not x % t]), None)

请注意，使用random.sample()的原因是它返回结果，而不像random.shuffle()在原列表上进行操作。如果您更喜欢random.shuffle()，并且不想在表达式中重复包含数字，您可以尝试以下方法：

next((x for x in (lambda y: random.shuffle(y) or y)(list(range(5000, 5200))) if not [t for t in range(2, x) if not x % t]), None)

- cdlane

---

由于这个答案侧重于性能，我想知道是否构建一个埃拉托斯特尼筛法，然后在所需范围内随机选择一个值不会更快（即使更消耗内存...） - Serge Ballesta

Answer 3

这里是更高效方案的一步。不要根据所有可能的除数测试素性的每个数字，而是保留预生成素数列表。

接下来，当我们准备在范围内选择一个随机素数时，使用二分法有效地找到所有有效答案的列表，并随机选择一个。如果这样的列表为空，则返回None。

from __future__ import print_function
import bisect
import random
from itertools import takewhile


class Primes(object):
    def __init__(self):
        self.primes = [2, 3]
        self.candidate = 5

    def process_candidate(self):
        if all(self.candidate % p != 0 for p in takewhile(
            lambda x: x * x <= self.candidate, self.primes)):
            self.primes.append(self.candidate)
        self.candidate += 2

    def maybe_random_prime_from_range(self, a, b):
        if b < a:
            return None

        while self.candidate < b:
            self.process_candidate()

        ai = bisect.bisect(self.primes, a)
        bi = bisect.bisect(self.primes[ai:], b)

        try:
            return random.choice(self.primes[ai:ai+bi])
        except:
            return None

ps = Primes()

print(ps.maybe_random_prime_from_range(4000, 4200))

- hilberts_drinking_problem

Answer 4

你的程序几乎正确，只需要随机选择即可完成。但是我想指出它浪费了很多时间。我用一种更高效的方式写了同样的代码。

import random
from math import sqrt

def prime(x):
    if x%2==0:return False
    elif any(x%i==0 for i in xrange(3,int(sqrt(x))+1,2)):return False
    else:return True

prime_list=[x for x in xrange(5000,5200) if prime(x)]

print random.choice(prime_list)

- Eular