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