Creating only one random prime number in provided range

Question

I want to create only one random prime number in any provided range. I have this code:

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

But my program provides a set of prime numbers. I want to modify my code and create only one random number in any provided range but I can't find how to do it. Help please.

Answer 1

My issue with mathmax's solution is that it does all the work to find the primes between 5000 and 5200 just to pick one and toss the rest. It might be more efficient to randomly pick unique numbers between 5000 and 5200 until you find the first one that's a prime:

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)

This is about 18x faster. We can get another 18x improvement over this by being a little smarter about our primality testing:

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)

Note that random.sample() is used as it returns a result unlike random.shuffle() that operates on the list in place. If you'd prefer random.shuffle(), and not including the numbers in the expression twice, you can instead do something like:

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)

Answer 2

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

Actually you are almost there, you just need to use random.choice()

---

Method 2:

Otherwise you can use permutation to randomly permute your prime number range and then pick the first element:

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]

Answer 3

Here is one step towards a more efficient solution. Instead of testing each number of primality based on all possible divisors, keep a list of pre-generated primes.

Next, when we are ready to pick a random prime in range, we use bisection to efficiently find the list of all valid answers and pick one at random. If such list is empty, return 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))