c++ - 在 C/C++ 中生成 2 个限制之间的随机素数

Question

是否有内置函数可以在 C/C++ 中的 2 个给定限制之间生成随机素数？

我想要一个可以生成 100 万到 10 亿之间的随机素数的函数

Answer 1

您可以像这样有效地做到这一点：

1. 在该区间内生成一个随机数；
2. 检查它是否可以被前几个素数中的任何一个整除（例如2 .. 17，实验以获得最佳结果）。如果是，转1；
3. 使用Miller-Rabin测试素数。

也可以看到这个类似的，更复杂的想法。

Answer 2

当我不得不这样做时，我创建了一个名为 isPrime() 的函数。isPrime() 将检查并确定一个数字是否为素数。

isPrime() 有两个不同的函数，一个将永远运行并打印每个素数，另一个将运行到某个数字。

您可以使用 i 和 j 之间的所有质数填充一个数组。然后生成一个小于或等于数组大小的随机数。使用此随机数从数组中选择一个元素。

希望这可以帮助！

Answer 3

要在两个边界之间生成一个随机数，请执行此操作

extern unsigned int urand();
int lower = 1000000;
int upper = 1000000000;
int p = urand() % (upper - lower) + lower;

要测试接近 10 亿的数是否为素数，只需将所有素数 < sqrt(10 亿) = 31622 进行试除即可。大约有 3400 个这样的素数。做一个数组

unsigned short primes[3400] = { 2, 3, 5, .. 31657 }

并除以他们。如果所有的试除法都有余数！= 0，那么这个数字是素数。

对于这么小的素数，我怀疑任何更复杂的素数测试都会更快。