Random prime in python

Question

I currently have ↓ installed as my randprime(p,q) function. Is there a way to condense this using something like genexp or listcomp ? Here is my function:

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

Answer 1

It’s better to just generate a list of primes, and then choose from this line. As is the case with your code, there is a subtle chance that it will end up in an infinite loop, either if there are no prime numbers in the intervals, or if randint always chooses a continuous one, then the while will never end.

So this is probably shorter and less troublesome:

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

Another advantage of this is the absence of deadlocks if there are no prime numbers in the intervals. As said, this can be slow depending on the range, so it would be faster if you fixed primes in advance:

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

Again, further optimizations are possible, but they depend very much on your actual code ... and you know what they say about premature optimizations.

Answer 2

So, it would be great if you could use an iterator so that integers from p to q in random order (without replacement). I could not find a way to do this. The following will provide random integers in this range and will skip everything that has already been tested.

 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' 

The big advantage of this is that if you say that the range you are testing is just (14.15), your code will work forever. This code is guaranteed to give an answer if such a prime exists and tells you that there is none if such a prime does not exist. Obviously you can make it more compact, but I'm trying to show the logic.

Answer 3

This github link contains a python script to generate n random primes between two integers: Random-Prime-Integer

Answer 4

Here is a script written in python to generate n random primes between two specified integers:

 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) 

Answer 5

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

It starts with itertools.count () - it gives an infinite set.

Each number maps to a new random number in the range, itertools.imap (). imap is like a map, but returns an iterator, not a list - we don’t want to generate a list of elusive random numbers!

Then the first matching number is found and returned.

It works effectively even if p and q are very far apart - for example, 1 and 10 ** 30, which do not generate a complete list!

By the way, this is no more efficient than your code above, and it is much harder to understand at a glance - please note that the next programmer should read your code and just do it as you did above. This programmer may be to you in six months, when you forgot what this code was supposed to do!

PS - in practice, you can replace count () with xrange (range NOT!), For example. xrange((pq)**1.5+20) to make no more than the number of attempts (balanced between a limited test for small ranges and large ranges and no more than 1/2% probability of failure, if it can be successful), otherwise as suggested in another post, you can loop forever.

PPS - improvement: replacing random.randint(p,q) with random.randint(p,q)|1 - this makes the code twice as efficient, but eliminates the possibility that the result will be 2.