view raw
Capattax Capattax - 10 months ago 52
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.


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

    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.