smallprimes.c 6.7 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004
  1. #include "os.h"
  2. ulong smallprimes[1000] = {
  3. 2,
  4. 3,
  5. 5,
  6. 7,
  7. 11,
  8. 13,
  9. 17,
  10. 19,
  11. 23,
  12. 29,
  13. 31,
  14. 37,
  15. 41,
  16. 43,
  17. 47,
  18. 53,
  19. 59,
  20. 61,
  21. 67,
  22. 71,
  23. 73,
  24. 79,
  25. 83,
  26. 89,
  27. 97,
  28. 101,
  29. 103,
  30. 107,
  31. 109,
  32. 113,
  33. 127,
  34. 131,
  35. 137,
  36. 139,
  37. 149,
  38. 151,
  39. 157,
  40. 163,
  41. 167,
  42. 173,
  43. 179,
  44. 181,
  45. 191,
  46. 193,
  47. 197,
  48. 199,
  49. 211,
  50. 223,
  51. 227,
  52. 229,
  53. 233,
  54. 239,
  55. 241,
  56. 251,
  57. 257,
  58. 263,
  59. 269,
  60. 271,
  61. 277,
  62. 281,
  63. 283,
  64. 293,
  65. 307,
  66. 311,
  67. 313,
  68. 317,
  69. 331,
  70. 337,
  71. 347,
  72. 349,
  73. 353,
  74. 359,
  75. 367,
  76. 373,
  77. 379,
  78. 383,
  79. 389,
  80. 397,
  81. 401,
  82. 409,
  83. 419,
  84. 421,
  85. 431,
  86. 433,
  87. 439,
  88. 443,
  89. 449,
  90. 457,
  91. 461,
  92. 463,
  93. 467,
  94. 479,
  95. 487,
  96. 491,
  97. 499,
  98. 503,
  99. 509,
  100. 521,
  101. 523,
  102. 541,
  103. 547,
  104. 557,
  105. 563,
  106. 569,
  107. 571,
  108. 577,
  109. 587,
  110. 593,
  111. 599,
  112. 601,
  113. 607,
  114. 613,
  115. 617,
  116. 619,
  117. 631,
  118. 641,
  119. 643,
  120. 647,
  121. 653,
  122. 659,
  123. 661,
  124. 673,
  125. 677,
  126. 683,
  127. 691,
  128. 701,
  129. 709,
  130. 719,
  131. 727,
  132. 733,
  133. 739,
  134. 743,
  135. 751,
  136. 757,
  137. 761,
  138. 769,
  139. 773,
  140. 787,
  141. 797,
  142. 809,
  143. 811,
  144. 821,
  145. 823,
  146. 827,
  147. 829,
  148. 839,
  149. 853,
  150. 857,
  151. 859,
  152. 863,
  153. 877,
  154. 881,
  155. 883,
  156. 887,
  157. 907,
  158. 911,
  159. 919,
  160. 929,
  161. 937,
  162. 941,
  163. 947,
  164. 953,
  165. 967,
  166. 971,
  167. 977,
  168. 983,
  169. 991,
  170. 997,
  171. 1009,
  172. 1013,
  173. 1019,
  174. 1021,
  175. 1031,
  176. 1033,
  177. 1039,
  178. 1049,
  179. 1051,
  180. 1061,
  181. 1063,
  182. 1069,
  183. 1087,
  184. 1091,
  185. 1093,
  186. 1097,
  187. 1103,
  188. 1109,
  189. 1117,
  190. 1123,
  191. 1129,
  192. 1151,
  193. 1153,
  194. 1163,
  195. 1171,
  196. 1181,
  197. 1187,
  198. 1193,
  199. 1201,
  200. 1213,
  201. 1217,
  202. 1223,
  203. 1229,
  204. 1231,
  205. 1237,
  206. 1249,
  207. 1259,
  208. 1277,
  209. 1279,
  210. 1283,
  211. 1289,
  212. 1291,
  213. 1297,
  214. 1301,
  215. 1303,
  216. 1307,
  217. 1319,
  218. 1321,
  219. 1327,
  220. 1361,
  221. 1367,
  222. 1373,
  223. 1381,
  224. 1399,
  225. 1409,
  226. 1423,
  227. 1427,
  228. 1429,
  229. 1433,
  230. 1439,
  231. 1447,
  232. 1451,
  233. 1453,
  234. 1459,
  235. 1471,
  236. 1481,
  237. 1483,
  238. 1487,
  239. 1489,
  240. 1493,
  241. 1499,
  242. 1511,
  243. 1523,
  244. 1531,
  245. 1543,
  246. 1549,
  247. 1553,
  248. 1559,
  249. 1567,
  250. 1571,
  251. 1579,
  252. 1583,
  253. 1597,
  254. 1601,
  255. 1607,
  256. 1609,
  257. 1613,
  258. 1619,
  259. 1621,
  260. 1627,
  261. 1637,
  262. 1657,
  263. 1663,
  264. 1667,
  265. 1669,
  266. 1693,
  267. 1697,
  268. 1699,
  269. 1709,
  270. 1721,
  271. 1723,
  272. 1733,
  273. 1741,
  274. 1747,
  275. 1753,
  276. 1759,
  277. 1777,
  278. 1783,
  279. 1787,
  280. 1789,
  281. 1801,
  282. 1811,
  283. 1823,
  284. 1831,
  285. 1847,
  286. 1861,
  287. 1867,
  288. 1871,
  289. 1873,
  290. 1877,
  291. 1879,
  292. 1889,
  293. 1901,
  294. 1907,
  295. 1913,
  296. 1931,
  297. 1933,
  298. 1949,
  299. 1951,
  300. 1973,
  301. 1979,
  302. 1987,
  303. 1993,
  304. 1997,
  305. 1999,
  306. 2003,
  307. 2011,
  308. 2017,
  309. 2027,
  310. 2029,
  311. 2039,
  312. 2053,
  313. 2063,
  314. 2069,
  315. 2081,
  316. 2083,
  317. 2087,
  318. 2089,
  319. 2099,
  320. 2111,
  321. 2113,
  322. 2129,
  323. 2131,
  324. 2137,
  325. 2141,
  326. 2143,
  327. 2153,
  328. 2161,
  329. 2179,
  330. 2203,
  331. 2207,
  332. 2213,
  333. 2221,
  334. 2237,
  335. 2239,
  336. 2243,
  337. 2251,
  338. 2267,
  339. 2269,
  340. 2273,
  341. 2281,
  342. 2287,
  343. 2293,
  344. 2297,
  345. 2309,
  346. 2311,
  347. 2333,
  348. 2339,
  349. 2341,
  350. 2347,
  351. 2351,
  352. 2357,
  353. 2371,
  354. 2377,
  355. 2381,
  356. 2383,
  357. 2389,
  358. 2393,
  359. 2399,
  360. 2411,
  361. 2417,
  362. 2423,
  363. 2437,
  364. 2441,
  365. 2447,
  366. 2459,
  367. 2467,
  368. 2473,
  369. 2477,
  370. 2503,
  371. 2521,
  372. 2531,
  373. 2539,
  374. 2543,
  375. 2549,
  376. 2551,
  377. 2557,
  378. 2579,
  379. 2591,
  380. 2593,
  381. 2609,
  382. 2617,
  383. 2621,
  384. 2633,
  385. 2647,
  386. 2657,
  387. 2659,
  388. 2663,
  389. 2671,
  390. 2677,
  391. 2683,
  392. 2687,
  393. 2689,
  394. 2693,
  395. 2699,
  396. 2707,
  397. 2711,
  398. 2713,
  399. 2719,
  400. 2729,
  401. 2731,
  402. 2741,
  403. 2749,
  404. 2753,
  405. 2767,
  406. 2777,
  407. 2789,
  408. 2791,
  409. 2797,
  410. 2801,
  411. 2803,
  412. 2819,
  413. 2833,
  414. 2837,
  415. 2843,
  416. 2851,
  417. 2857,
  418. 2861,
  419. 2879,
  420. 2887,
  421. 2897,
  422. 2903,
  423. 2909,
  424. 2917,
  425. 2927,
  426. 2939,
  427. 2953,
  428. 2957,
  429. 2963,
  430. 2969,
  431. 2971,
  432. 2999,
  433. 3001,
  434. 3011,
  435. 3019,
  436. 3023,
  437. 3037,
  438. 3041,
  439. 3049,
  440. 3061,
  441. 3067,
  442. 3079,
  443. 3083,
  444. 3089,
  445. 3109,
  446. 3119,
  447. 3121,
  448. 3137,
  449. 3163,
  450. 3167,
  451. 3169,
  452. 3181,
  453. 3187,
  454. 3191,
  455. 3203,
  456. 3209,
  457. 3217,
  458. 3221,
  459. 3229,
  460. 3251,
  461. 3253,
  462. 3257,
  463. 3259,
  464. 3271,
  465. 3299,
  466. 3301,
  467. 3307,
  468. 3313,
  469. 3319,
  470. 3323,
  471. 3329,
  472. 3331,
  473. 3343,
  474. 3347,
  475. 3359,
  476. 3361,
  477. 3371,
  478. 3373,
  479. 3389,
  480. 3391,
  481. 3407,
  482. 3413,
  483. 3433,
  484. 3449,
  485. 3457,
  486. 3461,
  487. 3463,
  488. 3467,
  489. 3469,
  490. 3491,
  491. 3499,
  492. 3511,
  493. 3517,
  494. 3527,
  495. 3529,
  496. 3533,
  497. 3539,
  498. 3541,
  499. 3547,
  500. 3557,
  501. 3559,
  502. 3571,
  503. 3581,
  504. 3583,
  505. 3593,
  506. 3607,
  507. 3613,
  508. 3617,
  509. 3623,
  510. 3631,
  511. 3637,
  512. 3643,
  513. 3659,
  514. 3671,
  515. 3673,
  516. 3677,
  517. 3691,
  518. 3697,
  519. 3701,
  520. 3709,
  521. 3719,
  522. 3727,
  523. 3733,
  524. 3739,
  525. 3761,
  526. 3767,
  527. 3769,
  528. 3779,
  529. 3793,
  530. 3797,
  531. 3803,
  532. 3821,
  533. 3823,
  534. 3833,
  535. 3847,
  536. 3851,
  537. 3853,
  538. 3863,
  539. 3877,
  540. 3881,
  541. 3889,
  542. 3907,
  543. 3911,
  544. 3917,
  545. 3919,
  546. 3923,
  547. 3929,
  548. 3931,
  549. 3943,
  550. 3947,
  551. 3967,
  552. 3989,
  553. 4001,
  554. 4003,
  555. 4007,
  556. 4013,
  557. 4019,
  558. 4021,
  559. 4027,
  560. 4049,
  561. 4051,
  562. 4057,
  563. 4073,
  564. 4079,
  565. 4091,
  566. 4093,
  567. 4099,
  568. 4111,
  569. 4127,
  570. 4129,
  571. 4133,
  572. 4139,
  573. 4153,
  574. 4157,
  575. 4159,
  576. 4177,
  577. 4201,
  578. 4211,
  579. 4217,
  580. 4219,
  581. 4229,
  582. 4231,
  583. 4241,
  584. 4243,
  585. 4253,
  586. 4259,
  587. 4261,
  588. 4271,
  589. 4273,
  590. 4283,
  591. 4289,
  592. 4297,
  593. 4327,
  594. 4337,
  595. 4339,
  596. 4349,
  597. 4357,
  598. 4363,
  599. 4373,
  600. 4391,
  601. 4397,
  602. 4409,
  603. 4421,
  604. 4423,
  605. 4441,
  606. 4447,
  607. 4451,
  608. 4457,
  609. 4463,
  610. 4481,
  611. 4483,
  612. 4493,
  613. 4507,
  614. 4513,
  615. 4517,
  616. 4519,
  617. 4523,
  618. 4547,
  619. 4549,
  620. 4561,
  621. 4567,
  622. 4583,
  623. 4591,
  624. 4597,
  625. 4603,
  626. 4621,
  627. 4637,
  628. 4639,
  629. 4643,
  630. 4649,
  631. 4651,
  632. 4657,
  633. 4663,
  634. 4673,
  635. 4679,
  636. 4691,
  637. 4703,
  638. 4721,
  639. 4723,
  640. 4729,
  641. 4733,
  642. 4751,
  643. 4759,
  644. 4783,
  645. 4787,
  646. 4789,
  647. 4793,
  648. 4799,
  649. 4801,
  650. 4813,
  651. 4817,
  652. 4831,
  653. 4861,
  654. 4871,
  655. 4877,
  656. 4889,
  657. 4903,
  658. 4909,
  659. 4919,
  660. 4931,
  661. 4933,
  662. 4937,
  663. 4943,
  664. 4951,
  665. 4957,
  666. 4967,
  667. 4969,
  668. 4973,
  669. 4987,
  670. 4993,
  671. 4999,
  672. 5003,
  673. 5009,
  674. 5011,
  675. 5021,
  676. 5023,
  677. 5039,
  678. 5051,
  679. 5059,
  680. 5077,
  681. 5081,
  682. 5087,
  683. 5099,
  684. 5101,
  685. 5107,
  686. 5113,
  687. 5119,
  688. 5147,
  689. 5153,
  690. 5167,
  691. 5171,
  692. 5179,
  693. 5189,
  694. 5197,
  695. 5209,
  696. 5227,
  697. 5231,
  698. 5233,
  699. 5237,
  700. 5261,
  701. 5273,
  702. 5279,
  703. 5281,
  704. 5297,
  705. 5303,
  706. 5309,
  707. 5323,
  708. 5333,
  709. 5347,
  710. 5351,
  711. 5381,
  712. 5387,
  713. 5393,
  714. 5399,
  715. 5407,
  716. 5413,
  717. 5417,
  718. 5419,
  719. 5431,
  720. 5437,
  721. 5441,
  722. 5443,
  723. 5449,
  724. 5471,
  725. 5477,
  726. 5479,
  727. 5483,
  728. 5501,
  729. 5503,
  730. 5507,
  731. 5519,
  732. 5521,
  733. 5527,
  734. 5531,
  735. 5557,
  736. 5563,
  737. 5569,
  738. 5573,
  739. 5581,
  740. 5591,
  741. 5623,
  742. 5639,
  743. 5641,
  744. 5647,
  745. 5651,
  746. 5653,
  747. 5657,
  748. 5659,
  749. 5669,
  750. 5683,
  751. 5689,
  752. 5693,
  753. 5701,
  754. 5711,
  755. 5717,
  756. 5737,
  757. 5741,
  758. 5743,
  759. 5749,
  760. 5779,
  761. 5783,
  762. 5791,
  763. 5801,
  764. 5807,
  765. 5813,
  766. 5821,
  767. 5827,
  768. 5839,
  769. 5843,
  770. 5849,
  771. 5851,
  772. 5857,
  773. 5861,
  774. 5867,
  775. 5869,
  776. 5879,
  777. 5881,
  778. 5897,
  779. 5903,
  780. 5923,
  781. 5927,
  782. 5939,
  783. 5953,
  784. 5981,
  785. 5987,
  786. 6007,
  787. 6011,
  788. 6029,
  789. 6037,
  790. 6043,
  791. 6047,
  792. 6053,
  793. 6067,
  794. 6073,
  795. 6079,
  796. 6089,
  797. 6091,
  798. 6101,
  799. 6113,
  800. 6121,
  801. 6131,
  802. 6133,
  803. 6143,
  804. 6151,
  805. 6163,
  806. 6173,
  807. 6197,
  808. 6199,
  809. 6203,
  810. 6211,
  811. 6217,
  812. 6221,
  813. 6229,
  814. 6247,
  815. 6257,
  816. 6263,
  817. 6269,
  818. 6271,
  819. 6277,
  820. 6287,
  821. 6299,
  822. 6301,
  823. 6311,
  824. 6317,
  825. 6323,
  826. 6329,
  827. 6337,
  828. 6343,
  829. 6353,
  830. 6359,
  831. 6361,
  832. 6367,
  833. 6373,
  834. 6379,
  835. 6389,
  836. 6397,
  837. 6421,
  838. 6427,
  839. 6449,
  840. 6451,
  841. 6469,
  842. 6473,
  843. 6481,
  844. 6491,
  845. 6521,
  846. 6529,
  847. 6547,
  848. 6551,
  849. 6553,
  850. 6563,
  851. 6569,
  852. 6571,
  853. 6577,
  854. 6581,
  855. 6599,
  856. 6607,
  857. 6619,
  858. 6637,
  859. 6653,
  860. 6659,
  861. 6661,
  862. 6673,
  863. 6679,
  864. 6689,
  865. 6691,
  866. 6701,
  867. 6703,
  868. 6709,
  869. 6719,
  870. 6733,
  871. 6737,
  872. 6761,
  873. 6763,
  874. 6779,
  875. 6781,
  876. 6791,
  877. 6793,
  878. 6803,
  879. 6823,
  880. 6827,
  881. 6829,
  882. 6833,
  883. 6841,
  884. 6857,
  885. 6863,
  886. 6869,
  887. 6871,
  888. 6883,
  889. 6899,
  890. 6907,
  891. 6911,
  892. 6917,
  893. 6947,
  894. 6949,
  895. 6959,
  896. 6961,
  897. 6967,
  898. 6971,
  899. 6977,
  900. 6983,
  901. 6991,
  902. 6997,
  903. 7001,
  904. 7013,
  905. 7019,
  906. 7027,
  907. 7039,
  908. 7043,
  909. 7057,
  910. 7069,
  911. 7079,
  912. 7103,
  913. 7109,
  914. 7121,
  915. 7127,
  916. 7129,
  917. 7151,
  918. 7159,
  919. 7177,
  920. 7187,
  921. 7193,
  922. 7207,
  923. 7211,
  924. 7213,
  925. 7219,
  926. 7229,
  927. 7237,
  928. 7243,
  929. 7247,
  930. 7253,
  931. 7283,
  932. 7297,
  933. 7307,
  934. 7309,
  935. 7321,
  936. 7331,
  937. 7333,
  938. 7349,
  939. 7351,
  940. 7369,
  941. 7393,
  942. 7411,
  943. 7417,
  944. 7433,
  945. 7451,
  946. 7457,
  947. 7459,
  948. 7477,
  949. 7481,
  950. 7487,
  951. 7489,
  952. 7499,
  953. 7507,
  954. 7517,
  955. 7523,
  956. 7529,
  957. 7537,
  958. 7541,
  959. 7547,
  960. 7549,
  961. 7559,
  962. 7561,
  963. 7573,
  964. 7577,
  965. 7583,
  966. 7589,
  967. 7591,
  968. 7603,
  969. 7607,
  970. 7621,
  971. 7639,
  972. 7643,
  973. 7649,
  974. 7669,
  975. 7673,
  976. 7681,
  977. 7687,
  978. 7691,
  979. 7699,
  980. 7703,
  981. 7717,
  982. 7723,
  983. 7727,
  984. 7741,
  985. 7753,
  986. 7757,
  987. 7759,
  988. 7789,
  989. 7793,
  990. 7817,
  991. 7823,
  992. 7829,
  993. 7841,
  994. 7853,
  995. 7867,
  996. 7873,
  997. 7877,
  998. 7879,
  999. 7883,
  1000. 7901,
  1001. 7907,
  1002. 7919,
  1003. };