1 2 2 3 3 5 4 11 5 13 6 17 7 19 8 29 9 37 10 41 11 43 12 53 13 59 14 61 15 67 16 83 17 97 18 101 19 107 20 109 21 113 22 131 23 137 24 139 25 149 26 157 27 163 28 173 29 179 30 181 31 193 32 197 33 211 34 227 35 229 36 241 37 251 38 257 39 269 40 277 41 281 42 283 43 293 44 307 45 313 46 317 47 331 48 347 49 349 50 353 51 373 52 379 53 389 54 397 55 401 56 409 57 419 58 421 59 433 60 443 61 449 62 457 63 461 64 467 65 491 66 499 67 509 68 521 69 523 70 541 71 547 72 557 73 563 74 569 75 571 76 577 77 587 78 593 79 613 80 617 81 619 82 641 83 643 84 653 85 659 86 661 87 673 88 677 89 683 90 691 91 701 92 709 93 733 94 739 95 757 96 761 97 769 98 773 99 787 100 797 101 809 102 811 103 821 104 827 105 829 106 853 107 857 108 859 109 877 110 883 111 907 112 929 113 941 114 947 115 953 116 971 117 977 118 997 119 1009 120 1013 121 1019 122 1021 123 1033 124 1049 125 1051 126 1061 127 1069 128 1091 129 1093 130 1097 131 1109 132 1117 133 1123 134 1129 135 1153 136 1163 137 1171 138 1181 139 1187 140 1193 141 1201 142 1213 143 1217 144 1229 145 1237 146 1249 147 1259 148 1277 149 1283 150 1291 151 1297 152 1301 153 1307 154 1321 155 1361 156 1373 157 1381 158 1409 159 1427 160 1429 161 1451 162 1453 163 1459 164 1481 165 1483 166 1489 167 1493 168 1499 169 1523 170 1531 171 1549 172 1553 173 1571 174 1579 175 1597 176 1601 177 1613 178 1619 179 1621 180 1627 181 1637 182 1657 183 1667 184 1669 185 1693 186 1697 187 1699 188 1709 189 1723 190 1733 191 1741 192 1747 193 1753 194 1777 195 1787 196 1789 197 1811 198 1861 199 1867 200 1873 201 1877 202 1889 203 1901 204 1907 205 1931 206 1933 207 1949 208 1973 209 1979 210 1987 211 1993 212 1997 213 2003 214 2011 215 2017 216 2027 217 2029 218 2053 219 2069 220 2081 221 2083 222 2099 223 2113 224 2129 225 2131 226 2137 227 2141 228 2153 229 2161 230 2179 231 2203 232 2213 233 2221 234 2237 235 2243 236 2251 237 2267 238 2269 239 2273 240 2281 241 2293 242 2297 243 2309 244 2333 245 2339 246 2341 247 2347 248 2357 249 2371 250 2377 251 2381 252 2389 253 2393 254 2411 255 2417 256 2437 257 2459 258 2467 259 2473 260 2477 261 2521 262 2531 263 2539 264 2549 265 2557 266 2579 267 2609 268 2617 269 2621 270 2633 271 2657 272 2659 273 2677 274 2683 275 2689 276 2693 277 2699 278 2707 279 2713 280 2729 281 2731 282 2741 283 2749 284 2753 285 2777 286 2789 287 2797 288 2801 289 2803 290 2819 291 2833 292 2837 293 2843 294 2851 295 2857 296 2861 297 2897 298 2909 299 2917 300 2939 301 2953 302 2957 303 2963 304 2971 305 3001 306 3011 307 3019 308 3037 309 3041 310 3049 311 3061 312 3067 313 3083 314 3089 315 3109 316 3121 317 3137 318 3163 319 3169 320 3181 321 3187 322 3203 323 3209 324 3217 325 3221 326 3229 327 3251 328 3253 329 3259 330 3299 331 3301 332 3307 333 3313 334 3323 335 3329 336 3331 337 3347 338 3361 339 3371 340 3373 341 3389 342 3413 343 3433 344 3457 345 3461 346 3467 347 3469 348 3491 349 3499 350 3517 351 3529 352 3533 353 3539 354 3541 355 3547 356 3557 357 3571 358 3581 359 3593 360 3613 361 3617 362 3637 363 3643 364 3659 365 3673 366 3677 367 3691 368 3697 369 3701 370 3709 371 3733 372 3739 373 3761 374 3769 375 3779 376 3793 377 3797 378 3803 379 3821 380 3833 381 3851 382 3853 383 3877 384 3881 385 3889 386 3907 387 3917 388 3923 389 3929 390 3931 391 3947 392 3989 393 4001 394 4003 395 4013 396 4019 397 4021 398 4027 399 4049 400 4051 401 4073 402 4091 403 4093 404 4099 405 4129 406 4133 407 4139 408 4153 409 4157 410 4211 411 4217 412 4219 413 4229 414 4241 415 4243 416 4253 417 4259 418 4261 419 4273 420 4283 421 4289 422 4337 423 4339 424 4349 425 4357 426 4363 427 4373 428 4397 429 4421 430 4441 431 4451 432 4457 433 4481 434 4483 435 4493 436 4507 437 4517 438 4523 439 4547 440 4549 441 4561 442 4597 443 4603 444 4621 445 4637 446 4643 447 4649 448 4651 449 4657 450 4673 451 4691 452 4723 453 4729 454 4733 455 4787 456 4789 457 4793 458 4801 459 4813 460 4817 461 4861 462 4877 463 4889 464 4909 465 4931 466 4933 467 4937 468 4957 469 4969 470 4973 471 4987 472 4993 473 5003 474 5009 475 5011 476 5021 477 5051 478 5059 479 5077 480 5099 481 5101 482 5107 483 5113 484 5147 485 5153 486 5171 487 5179 488 5189 489 5197 490 5227 491 5233 492 5237 493 5261 494 5273 495 5281 496 5297 497 5309 498 5323 499 5333 500 5347 501 5381 502 5387 503 5393 504 5413 505 5417 506 5419 507 5437 508 5441 509 5443 510 5449 511 5477 512 5483 513 5501 514 5507 515 5521 516 5531 517 5557 518 5563 519 5569 520 5573 521 5581 522 5641 523 5651 524 5653 525 5657 526 5659 527 5669 528 5683 529 5693 530 5701 531 5717 532 5741 533 5749 534 5779 535 5801 536 5813 537 5821 538 5827 539 5843 540 5849 541 5851 542 5857 543 5861 544 5867 545 5869 546 5881 547 5897 548 5923 549 5939 550 5953 551 5981 552 5987 553 6011 554 6029 555 6037 556 6043 557 6053 558 6067 559 6073 560 6091 561 6101 562 6113 563 6121 564 6131 565 6133 566 6163 567 6173 568 6197 569 6203 570 6211 571 6217 572 6221 573 6229 574 6257 575 6269 576 6277 577 6299 578 6301 579 6317 580 6323 581 6329 582 6337 583 6373 584 6379 585 6389 586 6397 587 6421 588 6427 589 6449 590 6451 591 6469 592 6473 593 6481 594 6491 595 6521 596 6529 597 6547 598 6563 599 6569 600 6571 601 6577 602 6581 603 6619 604 6637 605 6653 606 6659 607 6661 608 6673 609 6689 610 6691 611 6701 612 6709 613 6733 614 6737 615 6761 616 6763 617 6779 618 6781 619 6793 620 6803 621 6827 622 6829 623 6833 624 6841 625 6869 626 6883 627 6899 628 6907 629 6917 630 6947 631 6949 632 6961 633 6971 634 6977 635 6997 636 7001 637 7013 638 7019 639 7027 640 7043 641 7057 642 7069 643 7109 644 7121 645 7129 646 7177 647 7187 648 7193 649 7211 650 7213 651 7219 652 7229 653 7237 654 7243 655 7253 656 7283 657 7297 658 7307 659 7309 660 7321 661 7331 662 7333 663 7349 664 7369 665 7393 666 7411 667 7417 668 7433 669 7451 670 7457 671 7459 672 7477 673 7481 674 7489 675 7499 676 7507 677 7517 678 7523 679 7537 680 7541 681 7547 682 7549 683 7561 684 7573 685 7577 686 7589 687 7603 688 7621 689 7643 690 7649 691 7669 692 7673 693 7681 694 7691 695 7699 696 7717 697 7723 698 7741 699 7757 700 7789 701 7793 702 7817 703 7829 704 7841 705 7853 706 7867 707 7873 708 7877 709 7883 710 7901 711 7907 712 7933 713 7937 714 7949 715 7963 716 8009 717 8011 718 8017 719 8053 720 8059 721 8069 722 8081 723 8089 724 8093 725 8101 726 8117 727 8123 728 8147 729 8161 730 8171 731 8179 732 8209 733 8219 734 8221 735 8233 736 8237 737 8243 738 8269 739 8273 740 8291 741 8293 742 8297 743 8317 744 8329 745 8353 746 8363 747 8369 748 8377 749 8387 750 8389 751 8419 752 8429 753 8443 754 8461 755 8467 756 8501 757 8513 758 8521 759 8537 760 8539 761 8563 762 8573 763 8581 764 8597 765 8609 766 8627 767 8629 768 8641 769 8669 770 8677 771 8681 772 8689 773 8693 774 8699 775 8707 776 8731 777 8737 778 8741 779 8747 780 8753 781 8779 782 8803 783 8819 784 8821 785 8837 786 8849 787 8861 788 8867 789 8893 790 8923 791 8929 792 8933 793 8941 794 8963 795 8971 796 9001 797 9011 798 9013 799 9029 800 9041 801 9043 802 9049 803 9059 804 9067 805 9091 806 9109 807 9133 808 9137 809 9157 810 9161 811 9173 812 9181 813 9187 814 9203 815 9209 816 9221 817 9227 818 9241 819 9257 820 9277 821 9281 822 9283 823 9293 824 9323 825 9337 826 9341 827 9349 828 9371 829 9377 830 9397 831 9403 832 9413 833 9419 834 9421 835 9433 836 9437 837 9461 838 9467 839 9473 840 9491 841 9497 842 9521 843 9533 844 9539 845 9547 846 9587 847 9601 848 9613 849 9619 850 9629 851 9643 852 9649 853 9661 854 9677 855 9689 856 9697 857 9721 858 9733 859 9739 860 9749 861 9781 862 9787 863 9803 864 9811 865 9817 866 9829 867 9833 868 9851 869 9857 870 9859 871 9883 872 9901 873 9907 874 9923 875 9929 876 9931 877 9941 878 9949 879 9973 880 10009 881 10037 882 10061 883 10067 884 10069 885 10091 886 10093 887 10099 888 10133 889 10139 890 10141 891 10163 892 10169 893 10177 894 10181 895 10193 896 10211 897 10243 898 10253 899 10259 900 10267 901 10273 902 10289 903 10301 904 10313 905 10321 906 10331 907 10333 908 10337 909 10357 910 10369 911 10427 912 10429 913 10433 914 10453 915 10457 916 10459 917 10477 918 10499 919 10501 920 10513 921 10529 922 10531 923 10589 924 10597 925 10601 926 10613 927 10627 928 10651 929 10667 930 10691 931 10709 932 10723 933 10729 934 10733 935 10739 936 10753 937 10771 938 10781 939 10789 940 10837 941 10853 942 10859 943 10861 944 10867 945 10883 946 10889 947 10891 948 10909 949 10939 950 10949 951 10957 952 10973 953 10979 954 10987 955 10993 956 11003 957 11027 958 11057 959 11059 960 11069 961 11083 962 11093 963 11117 964 11131 965 11149 966 11161 967 11171 968 11173 969 11197 970 11213 971 11243 972 11251 973 11261 974 11273 975 11299 976 11317 977 11321 978 11329 979 11353 980 11369 981 11393 982 11411 983 11437 984 11443 985 11467 986 11483 987 11489 988 11491 989 11497 990 11549 991 11579 992 11587 993 11593 994 11597 995 11617 996 11621 997 11633 998 11677 999 11681 1000 11689