Capattax Capattax - 4 months ago 28
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.

Answer

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.

Comments