使用 c++11 std::uniform_int_distribution 生成随机素数

Question

正在尝试使用 C++11 std::uniform_int_distribution.

在 [2,2147483647] 范围内生成随机素数 p

有人评论说这种方法可能不正确：

It is not immediately obvious that this p is uniformly distributed over the set of all primes <= 2^31 - 1. Whatever uniformity and bias guarantees the random-number generator has, they refer to all integers within the range, but the code is "sieving" just the primes out of it.

然而，从另一篇类似的 S.O. 文章中，它指出

As long as the input random numbers are uniformly distributed in the range, the primes chosen by this method will be uniformly distributed among the primes in that range, too.

问题

这段代码真的能正确生成随机素数吗？

https://onlinegdb.com/FMzz78LBq

#include <stdio.h>
#include <stdint.h>
#include <math.h>
#include <time.h>
#include <random>


int isPrimeNumber (int num)
{
  if (num == 1) return 0;

  for (int i = 2; i <= sqrt (num); i++)
  {
      if (num % i == 0)
      {
        // not prime
        return 0;
      }
  }

  // prime
  return 1;
}

int main ()
{
  std::random_device rd;
  std::mt19937 rng (rd ());
  // Define prime range from 2 to 2^31 - 1.
  std::uniform_int_distribution<int>uni (2, 2147483647);

  int prime;

  // Generate a random prime.
  do { prime = uni(rng); } while (!isPrimeNumber(prime));

  printf ("prime = %d", prime);

  return 0;
}

Answer 1

您提供的代码：

在范围内统一选取一个随机素数。该范围内的任何给定素数与该范围内的任何其他素数出现的概率相同。
不会生成在整数范围内均匀分布的数字。例如。 1-1000 范围内的数字将比 1000001-1001000 范围内的数字多得多。
效率极低（如果你要生成很多数字）

您应该清楚自己想要什么。如果你想要上面的 2. 你需要一些不同的东西。

Answer 2

证明草图：

Assume for the purpose of contradiction that the algorithm produces a non-uniform distribution over the primes. Then there must be a prime p that has a higher probability than a prime q. As these are also integers, that means that in the larger range from 2 to N, sieving out non-primes had no effect on either p or q, hence the uniform distribution had to produce p with a higher probability than q, which is a direct contradiction.

Note: Observe that this proof would not hold if you compute a random number and search for the next prime after that number.

但是，正如 Jeffrey 指出的那样，该算法效率很低。想到一个替代方案：在 2**31 以内的范围内，您有大约 10**8 primes, according to the pi 函数。因此，仅创建一个包含所有这些素数的查找 table 并将其存储在一个单独的文件中（如果不在您的二进制文件中，我预计大约 400 MB）几乎是可行的，并且只需计算一个统一的随机数适当的间隔并从查找中选择该数字 table.

但是，为了安全起见，请注意，出于任何接近安全的目的，std::mt19937 不是加密安全 PRNG。

使用 c++11 std::uniform_int_distribution 生成随机素数

Generate a random prime using c++11 std::uniform_int_distribution

c++

primes