python - 在python中生成一个随机的非质数

Question

我如何在 Python 中生成一个范围内的非素数随机数？

我对如何创建一个算法来产生特定范围内的非素数感到困惑。我是定义函数还是创建条件语句？我希望范围内的每个数字都具有相同的概率。例如，在 1 - 100 中，每个非素数不会有 1% 的机会，而是有 ~1.35% 的机会。

Answer 1

现在，您没有说任何关于效率的事情，这肯定可以优化，但这应该可以解决问题。这应该是一种用于测试素数的有效算法:

import random

def isPrime(n):
    if n % 2 == 0 and n > 2: 
        return False

    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))

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)

返回范围内所有非素数的列表后，从非素数列表中选择一个随机值，使得选择范围内的任何非素数与范围内任何其他非素数的可能性一样.

编辑

虽然你没有问效率，但我很无聊，所以我想出了一个方法，使 (1000, 10000000) 的范围在我的上花费 6 秒多一点机器而不是超过一分半钟:

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)

这使用了 SymPy symbolic mathematics library优化一个范围内素数的生成，然后使用NumPy过滤我们的输出并选择一个随机的非素数。