cyaron icon indicating copy to clipboard operation
cyaron copied to clipboard

feat(math.py): Add the functionality to generate a random prime number within a specified range

Open weilycoder opened this issue 9 months ago • 0 comments

Update2: 另外,相关函数放在 math.py 中是否合理?


  • https://github.com/luogu-dev/cyaron/issues/163

算法不保证均匀随机,如果追求区间内每个质数被选中的概率相等,可以使用 prime_sieve 预处理质数表再使用 random 库中的 choice 函数。

具体流程如下:

  1. 在区间内随机一个数字;
  2. 判断这个数是否是质数,若是则立即返回;
  3. 寻找这个数字的下一个质数,若在范围内则立即返回;
  4. 寻找这个数字的上一个质数,若在范围内则立即返回;
  5. 范围内没有质数,报告错误。

Update: 已经对函数进行测试,与暴力查找进行了对拍,似乎没有问题


我为此实现的 nextprimeprevprime 都未经严格测试,大家可以先 review 一下(使用了大于 $3$ 的质数都是 $6n\pm 1$ 型的定理,逻辑略复杂)。

~~测试还没写,一会补上。~~

weilycoder avatar Feb 16 '25 09:02 weilycoder