（n+1）位十进制整数中的最小素数

无心人 · 发表于 2014-11-21 20:47:10

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

写了个程序计算小于\( 10^{1000} \)的整数中
\( 10^n + p, p > 0 \)形式的素数，针对每个\( n \)，最小的可能\( p \)值
即对应的\( n + 1 \)位整数中最小的可能素数

#include <gmp.h>
#include <stdio.h>
int main( void )
{
mpz_t a, b;
unsigned int i, t = 10, p, r;
mpz_init(a);
mpz_init(b);
printf("%4d: %d\n", 0, 2);
mpz_set_ui(a, 1);
for (i = 1; i < 1000; i ++)
{
mpz_mul_ui(a, a, t);
p = 1;
mpz_add_ui(b, a, p);
do
{
r = mpz_probab_prime_p(b, 25);
p += 2;
mpz_add_ui(b, b, 2);
} while (r == 0);
printf("%4d: %d\n", i, p-2);
}
mpz_clear(a);
mpz_clear(b);
}

复制代码

程序比较简单，就不解释了

无心人 · 发表于 2014-11-21 20:49:23

结果是

0: 2
1: 1
2: 1
3: 9
4: 7
5: 3
6: 3
7: 19
8: 7
9: 7
10: 19
11: 3
12: 39
13: 37
14: 31
15: 37
16: 61
17: 3
18: 3
19: 51
20: 39
21: 117
22: 9
23: 117
24: 7
25: 13
26: 67
27: 103
28: 331
29: 319
30: 57
31: 33
32: 49
33: 61
34: 193
35: 69
36: 67
37: 43
38: 133
39: 3
40: 121
41: 109
42: 63
43: 57
44: 31
45: 9
46: 121
47: 33
48: 193
49: 9
50: 151
51: 121
52: 327
53: 171
54: 31
55: 21
56: 3
57: 279
58: 159
59: 19
60: 7
61: 93
62: 447
63: 121
64: 57
65: 49
66: 49
67: 49
68: 99
69: 9
70: 33
71: 273
72: 39
73: 79
74: 207
75: 129
76: 133
77: 21
78: 93
79: 49
80: 129
81: 13
82: 391
83: 27
84: 261
85: 103
86: 151
87: 373
88: 181
89: 31
90: 289
91: 79
92: 399
93: 153
94: 97
95: 151
96: 127
97: 469
98: 49
99: 289
100: 267
101: 3
102: 117
103: 129
104: 267
105: 3
106: 79
107: 3
108: 19
109: 457
110: 7
111: 139
112: 207
113: 99
114: 271
115: 79
116: 93
117: 279
118: 709
119: 69
120: 79
121: 87
122: 1119
123: 3
124: 753
125: 237
126: 679
127: 283
128: 387
129: 459
130: 1113
131: 63
132: 169
133: 21
134: 7
135: 1143
136: 91
137: 283
138: 273
139: 513
140: 13
141: 129
142: 13
143: 81
144: 91
145: 73
146: 9
147: 987
148: 247
149: 183
150: 67
151: 901
152: 13
153: 87
154: 453
155: 189
156: 451
157: 583
158: 151
159: 187
160: 303
161: 403
162: 133
163: 217
164: 1527
165: 559
166: 267
167: 27
168: 1323
169: 37
170: 63
171: 193
172: 441
173: 337
174: 691
175: 339
176: 151
177: 723
178: 261
179: 979
180: 313
181: 217
182: 231
183: 999
184: 37
185: 927
186: 721
187: 163
188: 183
189: 181
190: 253
191: 57
192: 1153
193: 357
194: 951
195: 21
196: 39
197: 1107
198: 553
199: 153
200: 357
201: 97
202: 9
203: 181
204: 409
205: 483
206: 561
207: 163
208: 469
209: 103
210: 1129
211: 829
212: 237
213: 1027
214: 321
215: 201
216: 499
217: 169
218: 2319
219: 601
220: 427
221: 103
222: 7
223: 69
224: 139
225: 321
226: 229
227: 511
228: 37
229: 183
230: 753
231: 333
232: 1819
233: 151
234: 367
235: 213
236: 1081
237: 763
238: 691
239: 901
240: 1723
241: 97
242: 27
243: 759
244: 411
245: 117
246: 733
247: 651
248: 123
249: 1291
250: 1227
251: 391
252: 1599
253: 43
254: 267
255: 37
256: 141
257: 273
258: 133
259: 153
260: 49
261: 949
262: 741
263: 339
264: 1641
265: 261
266: 721
267: 1591
268: 501
269: 547
270: 361
271: 1191
272: 9
273: 663
274: 303
275: 693
276: 99
277: 1947
278: 273
279: 37
280: 13
281: 33
282: 1059
283: 399
284: 133
285: 399
286: 189
287: 231
288: 99
289: 1627
290: 279
291: 13
292: 303
293: 1617
294: 627
295: 423
296: 349
297: 271
298: 919
299: 669
300: 331
301: 531
302: 399
303: 237
304: 1549
305: 1089
306: 943
307: 657
308: 799
309: 1329
310: 733
311: 123
312: 81
313: 169
314: 2319
315: 1381
316: 627
317: 1159
318: 273
319: 1027
320: 699
321: 103
322: 781
323: 1921
324: 301
325: 649
326: 507
327: 2253
328: 1203
329: 549
330: 583
331: 1449
332: 921
333: 2389
334: 81
335: 483
336: 631
337: 181
338: 1497
339: 447
340: 1153
341: 831
342: 1243
343: 297
344: 1137
345: 1711
346: 2941
347: 103
348: 1557
349: 297
350: 133
351: 207
352: 1051
353: 1219
354: 1369
355: 129
356: 249
357: 21
358: 453
359: 693
360: 513
361: 589
362: 471
363: 667
364: 99
365: 117
366: 33
367: 217
368: 213
369: 1273
370: 2781
371: 129
372: 429
373: 387
374: 169
375: 1633
376: 1399
377: 579
378: 1893
379: 759
380: 387
381: 1939
382: 951
383: 291
384: 171
385: 1183
386: 763
387: 4449
388: 1617
389: 2241
390: 799
391: 477
392: 367
393: 453
394: 79
395: 109
396: 1321
397: 201
398: 829
399: 1311
400: 69
401: 1449
402: 807
403: 223
404: 63
405: 627
406: 13
407: 1053
408: 543
409: 387
410: 67
411: 231
412: 7
413: 3
414: 81
415: 1119
416: 123
417: 1141
418: 1321
419: 117
420: 1261
421: 129
422: 387
423: 1003
424: 627
425: 729
426: 3
427: 1443
428: 493
429: 957
430: 1587
431: 2059
432: 3901
433: 1609
434: 1149
435: 1081
436: 1743
437: 819
438: 537
439: 307
440: 709
441: 669
442: 961
443: 4593
444: 79
445: 1363
446: 1249
447: 759
448: 193
449: 99
450: 2269
451: 451
452: 1761
453: 363
454: 277
455: 147
456: 567
457: 499
458: 217
459: 523
460: 111
461: 777
462: 963
463: 3307
464: 639
465: 387
466: 1587
467: 363
468: 301
469: 31
470: 829
471: 1351
472: 1569
473: 99
474: 267
475: 217
476: 1723
477: 3391
478: 3603
479: 109
480: 2941
481: 733
482: 177
483: 1707
484: 67
485: 4891
486: 2731
487: 439
488: 961
489: 2109
490: 379
491: 1609
492: 427
493: 1623
494: 657
495: 1021
496: 1749
497: 591
498: 1527
499: 153
500: 961
501: 151
502: 1603
503: 523
504: 1713
505: 937
506: 493
507: 831
508: 1239
509: 657
510: 2523
511: 241
512: 231
513: 121
514: 2709
515: 2701
516: 79
517: 3157
518: 2323
519: 33
520: 343
521: 6537
522: 1713
523: 2991
524: 781
525: 559
526: 1801
527: 1177
528: 243
529: 181
530: 913
531: 1203
532: 33
533: 673
534: 3943
535: 3759
536: 1647
537: 3061
538: 1353
539: 1687
540: 2227
541: 733
542: 1677
543: 231
544: 1339
545: 649
546: 1291
547: 961
548: 487
549: 789
550: 2589
551: 817
552: 1699
553: 217
554: 937
555: 151
556: 2589
557: 1501
558: 2619
559: 1731
560: 847
561: 1789
562: 207
563: 1131
564: 2691
565: 171
566: 609
567: 3129
568: 501
569: 769
570: 667
571: 1869
572: 2961
573: 549
574: 19
575: 183
576: 3117
577: 4791
578: 2743
579: 2881
580: 789
581: 1581
582: 339
583: 2277
584: 829
585: 4419
586: 5049
587: 567
588: 267
589: 97
590: 169
591: 2247
592: 939
593: 1527
594: 789
595: 297
596: 1513
597: 4639
598: 421
599: 2161
600: 543
601: 1443
602: 2271
603: 103
604: 861
605: 279
606: 1821
607: 681
608: 567
609: 853
610: 103
611: 487
612: 1411
613: 493
614: 2629
615: 319
616: 2877
617: 2607
618: 2853
619: 621
620: 717
621: 613
622: 441
623: 1561
624: 187
625: 2203
626: 853
627: 3001
628: 2799
629: 19
630: 6883
631: 943
632: 37
633: 219
634: 2347
635: 879
636: 2739
637: 1107
638: 2323
639: 1269
640: 1983
641: 3003
642: 1003
643: 1741
644: 909
645: 109
646: 721
647: 5629
648: 243
649: 609
650: 1999
651: 247
652: 6249
653: 1963
654: 1089
655: 843
656: 3159
657: 1791
658: 51
659: 937
660: 1887
661: 313
662: 309
663: 6333
664: 3721
665: 123
666: 5289
667: 1423
668: 2593
669: 483
670: 187
671: 1207
672: 1383
673: 1291
674: 1347
675: 697
676: 39
677: 5593
678: 393
679: 399
680: 2277
681: 237
682: 291
683: 1599
684: 2461
685: 1683
686: 3403
687: 849
688: 4057
689: 1063
690: 3297
691: 1939
692: 3759
693: 1227
694: 1239
695: 73
696: 61
697: 1657
698: 1633
699: 1279
700: 7
701: 1377
702: 939
703: 157
704: 211
705: 1339
706: 1569
707: 349
708: 2931
709: 807
710: 171
711: 2359
712: 1029
713: 2299
714: 3117
715: 1861
716: 4369
717: 2901
718: 5863
719: 4807
720: 469
721: 3321
722: 4017
723: 3841
724: 3987
725: 6861
726: 1263
727: 273
728: 2983
729: 819
730: 1441
731: 1111
732: 91
733: 741
734: 489
735: 1609
736: 5077
737: 5461
738: 2151
739: 61
740: 283
741: 1533
742: 4143
743: 609
744: 679
745: 1279
746: 1413
747: 2457
748: 279
749: 823
750: 897
751: 283
752: 123
753: 283
754: 217
755: 2133
756: 1711
757: 2787
758: 1219
759: 531
760: 253
761: 1237
762: 5029
763: 427
764: 231
765: 1971
766: 3907
767: 1131
768: 949
769: 681
770: 139
771: 63
772: 3589
773: 957
774: 2163
775: 33
776: 1777
777: 1503
778: 709
779: 3889
780: 2847
781: 49
782: 541
783: 301
784: 111
785: 3529
786: 651
787: 3171
788: 139
789: 5613
790: 1191
791: 669
792: 751
793: 2661
794: 6789
795: 601
796: 4579
797: 1011
798: 187
799: 2409
800: 1537
801: 2239
802: 3271
803: 1383
804: 1113
805: 1861
806: 301
807: 3339
808: 3301
809: 1159
810: 1591
811: 1687
812: 1387
813: 621
814: 861
815: 4417
816: 553
817: 1567
818: 633
819: 10443
820: 433
821: 241
822: 453
823: 5691
824: 181
825: 2233
826: 1491
827: 7563
828: 1083
829: 4597
830: 2853
831: 1017
832: 5199
833: 99
834: 891
835: 79
836: 2809
837: 291
838: 247
839: 979
840: 4683
841: 421
842: 1129
843: 217
844: 177
845: 271
846: 733
847: 357
848: 301
849: 987
850: 1021
851: 927
852: 633
853: 381
854: 4701
855: 151
856: 5359
857: 409
858: 3199
859: 457
860: 2907
861: 2911
862: 1831
863: 1011
864: 3663
865: 1287
866: 2857
867: 1369
868: 2697
869: 907
870: 4519
871: 1473
872: 9621
873: 933
874: 2553
875: 9883
876: 691
877: 973
878: 829
879: 1423
880: 1819
881: 241
882: 2839
883: 6181
884: 759
885: 5161
886: 79
887: 493
888: 1519
889: 1983
890: 699
891: 597
892: 271
893: 937
894: 2739
895: 1011
896: 1119
897: 609
898: 5839
899: 201
900: 1873
901: 4011
902: 1683
903: 1021
904: 597
905: 4077
906: 403
907: 3871
908: 1113
909: 3567
910: 2191
911: 559
912: 2233
913: 1561
914: 909
915: 4087
916: 2809
917: 693
918: 3819
919: 1003
920: 601
921: 1777
922: 357
923: 4389
924: 4797
925: 2101
926: 5733
927: 2287
928: 331
929: 1797
930: 159
931: 943
932: 6103
933: 1551
934: 97
935: 1939
936: 2479
937: 5199
938: 249
939: 3007
940: 5047
941: 879
942: 829
943: 11467
944: 507
945: 1207
946: 4219
947: 2691
948: 607
949: 3681
950: 4273
951: 2061
952: 4827
953: 259
954: 1129
955: 2703
956: 4059
957: 1411
958: 973
959: 211
960: 501
961: 1077
962: 1431
963: 597
964: 651
965: 2229
966: 4749
967: 687
968: 2557
969: 433
970: 303
971: 411
972: 67
973: 121
974: 5383
975: 4081
976: 961
977: 229
978: 1867
979: 2613
980: 2989
981: 3831
982: 727
983: 2191
984: 1867
985: 1039
986: 997
987: 1771
988: 753
989: 1503
990: 1197
991: 547
992: 421
993: 7443
994: 831
995: 2013
996: 8823
997: 2437
998: 837
999: 7

复制代码

无心人 · 发表于 2014-11-21 21:13:52

原来想做个大的，计算到10000位，后来发现，想证明那么大的数是素数很难，
而到1000位，实际证明也是相当困难的，
所以，哪位有比较快速的证明程序，贡献一下，来证明这些数字的素性。

mathe · 发表于 2014-11-21 21:53:59

先要筛一下，直接判断太慢了，比如对于小素数q=3,5,7,...
可以先计算出10^n=h(mod q),于是10^n+k*q-h都不是素数，比如可以先用1000以内小素数筛一下，就可以少判断很多候选数了

无心人 · 发表于 2014-11-21 22:12:19

mathe 发表于 2014-11-21 21:53
先要筛一下，直接判断太慢了，比如对于小素数q=3,5,7,...
可以先计算出10^n=h(mod q),于是10^n+k*q-h都不 ...

嗯，我也想过这个，我这就是个测试程序，测试下这个问题有多难
结果是比预料的难度还大，主要是运行时间很长。
我打算筛到8192，以为足够了。
不过测试的结果范围有点窄，如果真算10000内的，估计范围要放的很大
那么问题来了，有的n，会很快找到可能素数，有的要几千个，
所以如何选择筛的范围是个大问题。

无心人 · 发表于 2014-11-22 16:39:25

上午做了初步编码，计划筛100万左右，
然后，发现预先筛选的时候，
基于10^n mod p的剩余
仅有2， 3， 5是只有唯一的可能
7,13有6种可能
11有2种可能
17有16种可能
导致预先筛选掉的素数只能是2， 3， 5
后来干脆穷举7， 11，13, 17的可能组合
用了位数组，此时内存占用144M
如果加上19，会有2.5G左右

mathe · 发表于 2014-11-22 19:00:11

10^n (mod p)动态计算也应该不是很难呀

无心人 · 发表于 2014-11-22 20:57:08

其实关键在于如何证明素性

无心人 · 发表于 2020-11-9 16:52:12

无心人发表于 2014-11-22 20:57
其实关键在于如何证明素性

现在感觉，N以2，3，5，7做强伪素数测试，然后，做frobenius的\( 1+\sqrt C \)形式的测试，通过测试的，应该能证明是素数，不是的概率应该远小于\( \frac{1}{\sqrt N} \)

mathe · 发表于 2020-11-9 16:59:57

确定性素性测试有AKS算法

账号		自动登录	找回密码
密码			欢迎注册

[原创] （n+1）位十进制整数中的最小素数

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

相关帖子