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

返回范围内所有非素数的列表后，从非素数列表中 select 随机值，使得范围内任何非素数的 selection与该范围内的任何其他非素数一样可能。

编辑

虽然你没有问效率，但我很无聊，所以我想出了一个方法，使 (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 to optimize the generation of prime numbers in a range, and then uses NumPy 过滤我们的输出和 select 一个随机的非素数。

Answer 2

如@smarx 所述，要选择的算法和想法在很大程度上取决于您的具体用例。

假设：

范围内的每个非素数被选中的概率相同/均匀性
采样数不是质数就足够了非常高的概率（算法误报的可能性低于CPU-bugs & co.）
采样范围可能很大（类似筛的方法很慢）
需要单个样本的高性能（无缓存；无替换无采样）

方法：

样本随机数在范围内
使用非常快速的概率素性测试
观察到第一个非素数时停止
如果没有找到数字，在max_trials
max_trials-值由优惠券收集者问题的近似值设置（wiki）：观察每个候选人一次的预期样本数

方法特点

单个样本快速（单个样本每秒 10000 个样本 CPU；给定范围如示例）
容易证明均匀性
关于范围大小和范围位置（数字大小）的良好渐近行为

代码

    import random
    import math

    """ Miller-Rabin primality test
            source: https://jeremykun.com/2013/06/16/miller-rabin-primality-test/
    """

    def decompose(n):
       exponentOfTwo = 0

       while n % 2 == 0:
          n = n//2  # modified for python 3!
          exponentOfTwo += 1

       return exponentOfTwo, n

    def isWitness(possibleWitness, p, exponent, remainder):
       possibleWitness = pow(possibleWitness, remainder, p)

       if possibleWitness == 1 or possibleWitness == p - 1:
          return False

       for _ in range(exponent):
          possibleWitness = pow(possibleWitness, 2, p)

          if possibleWitness == p - 1:
             return False

       return True

    def probablyPrime(p, accuracy=100):
       if p == 2 or p == 3: return True
       if p < 2: return False

       exponent, remainder = decompose(p - 1)

       for _ in range(accuracy):
          possibleWitness = random.randint(2, p - 2)
          if isWitness(possibleWitness, p, exponent, remainder):
             return False

       return True

    """ Coupon-Collector Problem (approximation)
            How many random-samplings with replacement are expected to observe each element at least once
    """
    def couponcollector(n):
        return int(n*math.log(n))

    """ Non-prime random-sampling
    """
    def get_random_nonprime(min, max):
        max_trials = couponcollector(max-min)
        for i in range(max_trials):
            candidate = random.randint(min, max)
            if not probablyPrime(candidate):
                return candidate
        return -1

    # TEST
    print(get_random_nonprime(1000, 10000000))

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

Generating a random, non-prime number in python

python

random

primes

python-3.x

假设：

方法：

方法特点

代码