怎么样求N以下所有素数

liangbch

这里给出完整的代码。

1. #include <stdio.h>
2. #include <tchar.h>
3. #include <windows.h>
4. #include <stdlib.h>
5. #include <time.h>
7. #include "include/gmp.h"
8. #pragma comment( lib, "lib/gmp.lib" /*"lib/gmp.lib"*/ )
10. #define MAX_BIT 2048
12. void SetFullF(char *p, int sizes) //全部填充为F
13. {
14. p[0] = 'F'; //保证达到特定大小
15. for (int i = 0; i < sizes; i ++)
16. {
17. p[i] = 'F';
18. }
19. p[i]=0;
20. }
22. void test_findPrime()
23. {
24. mpz_t gmp_N, gmp_r, gmp_q;
25. gmp_randstate_t state;
27. LARGE_INTEGER CountFreq, start, stop;
28. double UsedTime;
29. int bits;
30. char *pA;
32. bits=MAX_BIT;
33. QueryPerformanceFrequency(&CountFreq);
34. SetPriorityClass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS);
36. gmp_randinit_default(state); //设置随机初始状态
38. //初始化
39. mpz_init(gmp_N);
40. mpz_init(gmp_r);
41. mpz_init(gmp_q);
43. pA = (char *)malloc( bits/4 + 1 );
44. SetFullF(pA, bits/4);
45. mpz_set_str(gmp_N, pA, 16);
47. QueryPerformanceCounter(&start);
48. mpz_urandomm(gmp_r, state, gmp_N); //得到N以下随机一个数，赋给r
49. mpz_nextprime(gmp_q, gmp_r); //求得r的下一次素数，赋给q
50. QueryPerformanceCounter(&stop);
51. UsedTime = (double)(stop.QuadPart - start.QuadPart) / (double)CountFreq.QuadPart ;
53. gmp_printf ("n= %Zd\n", gmp_N);
54. gmp_printf ("r= %Zd\n", gmp_r);
55. gmp_printf ("q= %Zd\n", gmp_q);
56. printf("计算时间：%.3fs\n", UsedTime);
58. mpz_clear(gmp_N); //释放内存
59. mpz_clear(gmp_r); //释放内存
60. mpz_clear(gmp_q); //释放内存
61. }
64. int main(int argc, _TCHAR* argv[])
65. {
66. test_findPrime();
67. return 0;
68. return 0;
69. }

复制代码

liangbch

附加的信息： 1.我的代码参考了 http://bbs.emath.ac.cn/viewthread.php?tid=208 2. Windows下的GMP .h文件和.lib,.dll 文件下载自http://www.cs.nyu.edu/exact/core/gmp/ 3. 环境配置。在源代码下创建include 和 lib目录 并 复制dll文件到编译后可执行文件所在的目录。复制.h文件的到源代码下的./include目录，复制lib文件到./lib目录。 软件环境：Windows XP 2000 SP2, VC++6.0 硬件环境：Intel Core 2 Duo E8500， 4G内存。

gxqcn

因为要求“随机”，前后无关联，所以不好利用现成已有数据， 随机素数就按楼主的方法生成就可以了。 由于加解密的bits一般不会太高，所以速度一般是可以有保障的， 除非是频率非常低的嵌入式设备。

fly

22# liangbch 大哥，你确定懂C语言吗？我很难理解你说的不能终止啊？？ 那不能终止我为什么还能算出来。 你有没有把我的代码在你的计算上运行一下，看看真的不能终止呢？ 呃，难道你不知道mpz_cmp的用法？？我贴给你看吧 int mpz_cmp (mpz t op1, mpz t op2) Compare op1 and op2. Return a positive value if op1 > op2, zero if op1 = op2, or a negative value if op1 < op2. 还是你不清楚do,while的语法？？ do……while（表达式）的意思是如果表达式为真，则返回循环，否则跳出 我的代码的意思是 1. 随机生成一个N以下的整数r 2. 找到r的下一个素数r' 3. 如果r'比N大（你说这个概率为几乎为0，但你能保证概率是为0吗？我要的是绝对素数，不是几乎可能是素数），则返回1，2，否则跳出，得到一个比N小的素数。 概率几乎为0就等于我的循环几乎不用循环

fly

24# liangbch 我觉得啊（个人感觉） 你的代码里面除了 mpz_urandomm(gmp_r, state, gmp_N); //得到N以下随机一个数，赋给r mpz_nextprime(gmp_q, gmp_r); //求得r的下一次素数，赋给q 以外，其他的真正对算法有帮助的好像没有了。（这两句还是跟我一样的） 而且也找不到你说的“非确定素数判定法”的影子。（因为我的代码的读写能力很弱，可能看错了） 就算是有，我不觉得“非确定素数判定法”还能对已经产生的素数gmp_q有什么帮助？？ 所以你的代码实际上是我的代码的不完全版本。（我感觉，可能不对） 而且，如果gmp_r＝N－10（可能性小，但是毕竟会发生的，因为我加密是成千上万次的），你觉得你的算法会产生比N小的素数吗？ 不过你的速度好快，我要把试试看，看为什么我的会比你慢，因为从代码上来说，我的只会比你快的。 还是从你发的贴的获益不少，谢谢你！

fly

24# liangbch 这次用的时间不用一秒了，即时显示，我的计算机配置比你的差，用你的机子跑，应该更快。 原来是我的那些加密，解密，模幂用的时间长啊，郁闷啊 the modulus: 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656 the Random: 27362146563138776857982728818380223201396348785705792191523687503949678108173999405661271175052962670687188762919616768930398127110563727120090393377192663065339925106340896493856989857095594982576579810527282267125991883969347921691778215703198021881656810310840682707715049113743235773157119149858759547571693709281439277774520789443206541564734916342806365012658347347636233855537211097844890795221584089042680691894169980210638182168682463539762288035366855349499839748659172105286746228695779975747577204898312976788706805092864351507296077048907174491531725975477830513157574120773905306854649624870603675456839 主要代码如下，其他的头文件什么的不贴了 mpz_t n, r; mpz_init(n); mpz_init(r); mpz_ui_pow_ui(n,2,2048); gmp_randstate_t state; gmp_randinit_default(state); do { mpz_urandomm(r, state, n); mpz_nextprime(r, r); } while(mpz_cmp(r, n)>=0); gmp_printf("\n\nthe modulus: %Zd\n", n); gmp_printf("\n\nthe Random: %Zd\n", r); mpz_clear(n); mpz_clear(r);

fly

23# gxqcn 牛人，见解好透彻！ 你的意思是不是说如果要生成2^20个N以下素数，用我的代码重复2^20次就可以了吗？ 唉，我就是想得到这样一些比较实际有用的建议。

liangbch

26# fly 我的确理解错了do while 循环。 郑重向楼主致歉。我删除了我错误的断言。

liangbch

27# fly mpz_nextprime采用的是概率算法，即非确定性算法。16#的GMP帮助文档的文字已经说明，可能你忽略了，请重读一遍。

G-Spider

28# fly 因为随机值不存在依赖关系，不好利用之前的结果。 如果说是生产0~n之间的随机数，然后生成一个比n小的素数，可以 适当的缩小一下随机数范围到0~m (m