数学研发论坛

 找回密码
 欢迎注册
查看: 1221|回复: 7

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

[复制链接]
发表于 2014-11-21 20:47:10 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

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

  3. int main( void )
  4. {
  5.   mpz_t a, b;
  6.   unsigned int i, t = 10, p, r;
  7.   mpz_init(a);
  8.   mpz_init(b);
  9.   printf("%4d: %d\n", 0, 2);
  10.   mpz_set_ui(a, 1);
  11.   for (i = 1; i < 1000; i ++)
  12.   {
  13.     mpz_mul_ui(a, a, t);
  14.     p = 1;
  15.     mpz_add_ui(b, a, p);
  16.     do
  17.     {
  18.       r = mpz_probab_prime_p(b, 25);
  19.       p += 2;
  20.       mpz_add_ui(b, b, 2);
  21.     } while (r == 0);
  22.     printf("%4d: %d\n", i, p-2);
  23.   }
  24.   mpz_clear(a);
  25.   mpz_clear(b);
  26. }
复制代码

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

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-10-14 14:39 , Processed in 0.057335 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表