Capattax - 1 year ago 99
Python Question

# Generating a random, non-prime number in python

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.

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download