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.
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)