cyaron
cyaron copied to clipboard
feat(math.py): Add the functionality to generate a random prime number within a specified range
Update2: 另外,相关函数放在 math.py 中是否合理?
- https://github.com/luogu-dev/cyaron/issues/163
算法不保证均匀随机,如果追求区间内每个质数被选中的概率相等,可以使用 prime_sieve 预处理质数表再使用 random 库中的 choice 函数。
具体流程如下:
- 在区间内随机一个数字;
- 判断这个数是否是质数,若是则立即返回;
- 寻找这个数字的下一个质数,若在范围内则立即返回;
- 寻找这个数字的上一个质数,若在范围内则立即返回;
- 范围内没有质数,报告错误。
Update: 已经对函数进行测试,与暴力查找进行了对拍,似乎没有问题
我为此实现的 nextprime 和 prevprime 都未经严格测试,大家可以先 review 一下(使用了大于 $3$ 的质数都是 $6n\pm 1$ 型的定理,逻辑略复杂)。
~~测试还没写,一会补上。~~