Capattax - 1 year ago 71

Python Question

How would I generate a non-prime random number in a range in Python?

I am confused as to how I can create an algorithm that would produce a non-prime number in a certain range. Do I define a function or create a conditional statement? I would like each number in the range to have the same probability. For example, in 1 - 100, each non-prime would not have a 1% chance but instead has a ~1.35% chance.

Answer Source

Now, you didn't say anything about efficiency, and this could surely be optimized, but this should solve the problem. This (`isPrime()`

) uses the AKS Primality Test, which is supposed to be a very efficient algorithm:

```
import random
def isPrime(n):
if n == 2 or n == 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
(i, w) = (5, 2)
while i * i <= n:
if n % i == 0:
return False
i += w
w = 6 - w
return True
def randomNonPrime(rangeMin, rangeMax):
nonPrimes = filter(lambda n: not isPrime(n), xrange(rangeMin, rangeMax+1))
if not nonPrimes:
return None
return random.choice(nonPrimes)
minMax = (1000, 10000)
print randomNonPrime(*minMax)
```

After returning a list of all non-primes in range, a random value is selected from the list of non-primes, making the selection of any non-prime in range just as likely as any other non-prime in the range.

**Edit**

Although you didn't ask about efficiency, I was bored, so I figured out a method of doing this that makes a range of `(1000, 10000000)`

take a little over 6 seconds on my machine instead of over a minute and a half:

```
import numpy
import sympy
def randomNonPrime(rangeMin, rangeMax):
primesInRange = numpy.fromiter(
sympy.sieve.primerange(rangeMin, rangeMax),
dtype=numpy.uint32,
count=-1
)
numbersInRange = numpy.arange(rangeMin, rangeMax+1, dtype=numpy.uint32)
nonPrimes = numbersInRange[numpy.invert(numpy.in1d(numbersInRange, primesInRange))]
if not nonPrimes.size:
return None
return numpy.random.choice(nonPrimes)
minMax = (1000, 10000000)
print randomNonPrime(*minMax)
```

This uses the SymPy symbolic mathematics library to optimize the generation of prime numbers in a range, and then uses NumPy to filter our output and select a random non-prime.