多次生成N以下的随机素数，利用GMP大数库

fly

关于随机得到N以下的一个素数，我自己是这么写的 gmp_randinit_default(state); 设置随机初始状态 do { mpz_urandomm(r, state, N); 得到N以下随机一个数，赋给r mpz_nextprime(r, r); 求得r的下一次素数，赋给r } while(mpz_cmp(r, N)>=0); 如果r>N，返回循环重新生成 如果只要得到一个随机素数的话，感觉还可以，不过从实验来看，利用的时间还是比较长的（N是一千比特的数）。而且我是用到很多个随机素数，所以感觉每次都要这么生成，效率不高。 所有求有没有什么算法可以在GMP下实现生成N以下所有素数N[x]。这样我只要从N[x]里面选一个就行。 谢谢各位啊！

fly

难道我的算法是最高效率地？？？

gxqcn

不知你的目的具体是什么？ 如果是想拿空间换时间，可以建一个大素数缓冲池，用一个剔除一个，低于下限时立即再生成一批。 而具体到每个大随机素数的生成，除了“生成随机整数-->搜索邻近大素数”的思路外，似乎也没有更好的算法， 毕竟素数至今并没有被发现“构造性”的算法，也就是说可通过公式直接确定出素数来， 当前的非确定性算法是比较快的，但基本的逻辑原理是采用“排除法”，不同算法之间的差异主要是“过滤”的强度以及效率间的差别而已。