Created
January 29, 2014 10:25
-
-
Save kunishi/8685267 to your computer and use it in GitHub Desktop.
ICPC 2007 Asia Region, Problem B
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| exception NotFoundException | |
| (* | |
| fun get_primes n = | |
| let | |
| open Array | |
| fun check array = | |
| let | |
| fun check_one n array = | |
| if not (sub (!array, n)) then () | |
| else modifyi (fn (i, x) => | |
| if i <= n then x | |
| else x andalso (i mod n <> 0)) (!array) | |
| val i = ref 1 | |
| in | |
| while (i := !i + 1; !i < Array.length (!array)) do | |
| check_one (!i) array; | |
| array | |
| end | |
| val prime_array = !(check (ref (Array.array (n, true)))) | |
| fun collect_primes 0 array result = result | |
| | collect_primes n array result = | |
| if sub (array, n-1) | |
| then collect_primes (n-1) array ((n-1)::result) | |
| else collect_primes (n-1) array result | |
| in | |
| List.filter (fn x => x >= 2) (collect_primes n prime_array nil) | |
| end | |
| *) | |
| fun get_primes n = | |
| let | |
| val l = List.tabulate (n, fn n => n + 2) | |
| fun get_primes_sub nil result = result | |
| | get_primes_sub (x::xs) result = | |
| get_primes_sub (List.filter (fn n => n mod x <> 0) xs) (x::result) | |
| in | |
| List.rev (get_primes_sub l nil) | |
| end | |
| fun solve_one n primes ppairs = | |
| case List.find (fn x => x = n) primes of | |
| SOME x => x | |
| | NONE => case List.find (fn (p, q) => p <= n andalso n < q) ppairs of | |
| SOME (p, q) => q - p | |
| | NONE => raise NotFoundException | |
| fun solve file = | |
| let | |
| open TextIO | |
| val primes = get_primes 1299720 | |
| val ppairs = ListPair.zip (primes, tl primes) | |
| val f = openIn file | |
| val line = ref NONE | |
| in | |
| while (line := inputLine f; !line <> SOME "0\n") do | |
| let | |
| val n = Int.fromString (valOf (!line)) | |
| in | |
| case n of | |
| SOME v => | |
| output (stdOut, | |
| Int.toString (solve_one v primes ppairs) ^ "\n") | |
| | NONE => raise NotFoundException | |
| end; | |
| closeIn f | |
| end |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 10 | |
| 11 | |
| 27 | |
| 2 | |
| 492170 | |
| 0 |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 2 | |
| 1299709 | |
| 492170 | |
| 370317 | |
| 1220967 | |
| 1159562 | |
| 1133057 | |
| 917295 | |
| 1264136 | |
| 500281 | |
| 92167 | |
| 58737 | |
| 517860 | |
| 1279143 | |
| 1099085 | |
| 474220 | |
| 948870 | |
| 1037827 | |
| 952245 | |
| 498957 | |
| 900107 | |
| 923642 | |
| 1074403 | |
| 938884 | |
| 48488 | |
| 1005233 | |
| 822261 | |
| 955767 | |
| 496287 | |
| 451875 | |
| 1064902 | |
| 1152059 | |
| 232357 | |
| 660857 | |
| 67365 | |
| 610156 | |
| 230011 | |
| 98746 | |
| 758178 | |
| 101094 | |
| 382282 | |
| 46270 | |
| 1279628 | |
| 683393 | |
| 388330 | |
| 577332 | |
| 535430 | |
| 348917 | |
| 381941 | |
| 768188 | |
| 903195 | |
| 1163716 | |
| 91781 | |
| 415330 | |
| 2267 | |
| 855848 | |
| 1205262 | |
| 961274 | |
| 338133 | |
| 228592 | |
| 1132590 | |
| 296613 | |
| 268030 | |
| 1102160 | |
| 218980 | |
| 146232 | |
| 449831 | |
| 799389 | |
| 743919 | |
| 181938 | |
| 1050656 | |
| 453771 | |
| 684111 | |
| 109321 | |
| 1225106 | |
| 200063 | |
| 149306 | |
| 984176 | |
| 102735 | |
| 1202327 | |
| 1241384 | |
| 1249067 | |
| 322180 | |
| 525300 | |
| 978170 | |
| 1064489 | |
| 676802 | |
| 1069756 | |
| 758271 | |
| 267907 | |
| 1186350 | |
| 570153 | |
| 362920 | |
| 1288855 | |
| 715876 | |
| 534112 | |
| 1074090 | |
| 21343 | |
| 1221243 | |
| 324852 | |
| 658769 | |
| 977402 | |
| 934256 | |
| 462554 | |
| 944594 | |
| 742271 | |
| 537609 | |
| 468452 | |
| 674003 | |
| 1142303 | |
| 139436 | |
| 970606 | |
| 1295609 | |
| 693977 | |
| 575572 | |
| 960920 | |
| 1254702 | |
| 196970 | |
| 398256 | |
| 169026 | |
| 29512 | |
| 920762 | |
| 1006309 | |
| 173367 | |
| 1133091 | |
| 403538 | |
| 204913 | |
| 174160 | |
| 21726 | |
| 31410 | |
| 273273 | |
| 1109226 | |
| 647602 | |
| 1171255 | |
| 629819 | |
| 62119 | |
| 1149459 | |
| 191816 | |
| 1236925 | |
| 123516 | |
| 573489 | |
| 1194699 | |
| 756933 | |
| 338807 | |
| 295222 | |
| 1054693 | |
| 857400 | |
| 693756 | |
| 105366 | |
| 1075044 | |
| 762502 | |
| 927563 | |
| 362897 | |
| 1117862 | |
| 1210879 | |
| 738304 | |
| 1160504 | |
| 66021 | |
| 455103 | |
| 55020 | |
| 761059 | |
| 864680 | |
| 848634 | |
| 1275859 | |
| 302221 | |
| 427525 | |
| 1134153 | |
| 864474 | |
| 447848 | |
| 1201264 | |
| 859530 | |
| 1248844 | |
| 792931 | |
| 1051316 | |
| 1022020 | |
| 1165553 | |
| 531104 | |
| 928664 | |
| 267057 | |
| 613858 | |
| 919482 | |
| 18583 | |
| 1104128 | |
| 573384 | |
| 389486 | |
| 331750 | |
| 302430 | |
| 129720 | |
| 550160 | |
| 968758 | |
| 576228 | |
| 1257793 | |
| 555736 | |
| 654496 | |
| 740910 | |
| 737627 | |
| 12945 | |
| 265924 | |
| 439064 | |
| 533802 | |
| 938444 | |
| 672149 | |
| 411342 | |
| 1037419 | |
| 459592 | |
| 960800 | |
| 835176 | |
| 1078108 | |
| 131973 | |
| 594818 | |
| 1262310 | |
| 117655 | |
| 1293948 | |
| 418706 | |
| 1033771 | |
| 233681 | |
| 39557 | |
| 1292588 | |
| 762003 | |
| 1065751 | |
| 406523 | |
| 1087993 | |
| 170486 | |
| 596405 | |
| 447769 | |
| 692918 | |
| 1097180 | |
| 878503 | |
| 684218 | |
| 219950 | |
| 712581 | |
| 551667 | |
| 772984 | |
| 891799 | |
| 1068590 | |
| 695817 | |
| 992552 | |
| 44690 | |
| 703461 | |
| 57296 | |
| 1184912 | |
| 276502 | |
| 194708 | |
| 18846 | |
| 144778 | |
| 240827 | |
| 200376 | |
| 452408 | |
| 848671 | |
| 695304 | |
| 1108388 | |
| 674098 | |
| 144646 | |
| 1117993 | |
| 945319 | |
| 73210 | |
| 648404 | |
| 741570 | |
| 399705 | |
| 1096033 | |
| 648248 | |
| 332629 | |
| 849071 | |
| 1187391 | |
| 354204 | |
| 499667 | |
| 273512 | |
| 1097205 | |
| 879689 | |
| 205668 | |
| 1178594 | |
| 558994 | |
| 7712 | |
| 1062351 | |
| 1017641 | |
| 531810 | |
| 1236159 | |
| 705046 | |
| 465675 | |
| 23004 | |
| 78793 | |
| 235627 | |
| 8038 | |
| 1156280 | |
| 570395 | |
| 1051328 | |
| 133646 | |
| 995534 | |
| 947943 | |
| 298734 | |
| 934713 | |
| 1193333 | |
| 721370 | |
| 509863 | |
| 1050668 | |
| 544148 | |
| 334745 | |
| 635999 | |
| 677882 | |
| 724625 | |
| 1127478 | |
| 1233847 | |
| 673622 | |
| 669056 | |
| 262797 | |
| 403632 | |
| 99145 | |
| 425854 | |
| 1190457 | |
| 624222 | |
| 398275 | |
| 574826 | |
| 265495 | |
| 150518 | |
| 1272609 | |
| 470305 | |
| 1273946 | |
| 537003 | |
| 56422 | |
| 226153 | |
| 1055061 | |
| 398634 | |
| 346446 | |
| 232854 | |
| 619356 | |
| 1237829 | |
| 192254 | |
| 329430 | |
| 1110544 | |
| 433459 | |
| 50248 | |
| 270227 | |
| 1222431 | |
| 1045998 | |
| 879471 | |
| 1018114 | |
| 259898 | |
| 110242 | |
| 869352 | |
| 355700 | |
| 272759 | |
| 98462 | |
| 619800 | |
| 511959 | |
| 74193 | |
| 487780 | |
| 313310 | |
| 1045077 | |
| 605120 | |
| 895626 | |
| 1281951 | |
| 158660 | |
| 1027897 | |
| 636925 | |
| 310334 | |
| 968935 | |
| 437903 | |
| 457279 | |
| 104408 | |
| 1070110 | |
| 40276 | |
| 190482 | |
| 846430 | |
| 1135799 | |
| 1299099 | |
| 695427 | |
| 343427 | |
| 73787 | |
| 945079 | |
| 50339 | |
| 969809 | |
| 323149 | |
| 879161 | |
| 897843 | |
| 75381 | |
| 782753 | |
| 747631 | |
| 1084139 | |
| 302945 | |
| 813551 | |
| 156640 | |
| 981371 | |
| 789295 | |
| 1259671 | |
| 499465 | |
| 891107 | |
| 1015896 | |
| 803472 | |
| 463289 | |
| 1090054 | |
| 294981 | |
| 641246 | |
| 682813 | |
| 1024313 | |
| 41993 | |
| 959499 | |
| 309195 | |
| 168131 | |
| 718184 | |
| 548339 | |
| 307020 | |
| 405099 | |
| 1280145 | |
| 567733 | |
| 1130886 | |
| 1017226 | |
| 821418 | |
| 682342 | |
| 464639 | |
| 863177 | |
| 1196285 | |
| 174453 | |
| 1130911 | |
| 727814 | |
| 753337 | |
| 424893 | |
| 1157696 | |
| 437389 | |
| 931919 | |
| 874919 | |
| 274593 | |
| 310514 | |
| 736269 | |
| 275362 | |
| 1295239 | |
| 589852 | |
| 980839 | |
| 1145605 | |
| 1247056 | |
| 632486 | |
| 1016092 | |
| 338802 | |
| 929520 | |
| 1047626 | |
| 273760 | |
| 661964 | |
| 1207954 | |
| 37340 | |
| 1289147 | |
| 204756 | |
| 1293494 | |
| 1190034 | |
| 224822 | |
| 598176 | |
| 916598 | |
| 576624 | |
| 969879 | |
| 448902 | |
| 629455 | |
| 966713 | |
| 105613 | |
| 257460 | |
| 1199088 | |
| 152741 | |
| 645441 | |
| 432758 | |
| 740739 | |
| 260587 | |
| 415266 | |
| 946844 | |
| 176167 | |
| 1281713 | |
| 497370 | |
| 681013 | |
| 687153 | |
| 165334 | |
| 1256023 | |
| 827659 | |
| 31985 | |
| 1299579 | |
| 1002151 | |
| 770932 | |
| 893197 | |
| 989862 | |
| 45553 | |
| 1259096 | |
| 1227957 | |
| 382808 | |
| 76337 | |
| 551736 | |
| 1151587 | |
| 110864 | |
| 759848 | |
| 409453 | |
| 1174826 | |
| 322921 | |
| 182655 | |
| 67970 | |
| 610012 | |
| 292828 | |
| 406097 | |
| 65962 | |
| 1180117 | |
| 1064191 | |
| 169437 | |
| 712476 | |
| 869862 | |
| 1018312 | |
| 23100 | |
| 745610 | |
| 564955 | |
| 154229 | |
| 1068381 | |
| 339175 | |
| 935465 | |
| 835656 | |
| 1103066 | |
| 257882 | |
| 73768 | |
| 475593 | |
| 157742 | |
| 33689 | |
| 1209328 | |
| 1153819 | |
| 517275 | |
| 527081 | |
| 688484 | |
| 255868 | |
| 814781 | |
| 158714 | |
| 438460 | |
| 284392 | |
| 1152735 | |
| 398462 | |
| 699562 | |
| 1154983 | |
| 822648 | |
| 23028 | |
| 1265713 | |
| 755787 | |
| 1136231 | |
| 1109870 | |
| 1256956 | |
| 1207135 | |
| 264326 | |
| 490460 | |
| 672671 | |
| 1235123 | |
| 432151 | |
| 817950 | |
| 548086 | |
| 1006479 | |
| 1158011 | |
| 843080 | |
| 307384 | |
| 730425 | |
| 751378 | |
| 1201695 | |
| 688824 | |
| 806749 | |
| 439047 | |
| 800400 | |
| 1089418 | |
| 446544 | |
| 274883 | |
| 130563 | |
| 1192821 | |
| 672328 | |
| 310041 | |
| 938135 | |
| 355805 | |
| 739301 | |
| 1039672 | |
| 1150611 | |
| 218466 | |
| 497366 | |
| 1052982 | |
| 1050009 | |
| 315308 | |
| 290722 | |
| 110467 | |
| 826135 | |
| 497163 | |
| 1177590 | |
| 662592 | |
| 455741 | |
| 450174 | |
| 923943 | |
| 887660 | |
| 845752 | |
| 915631 | |
| 573330 | |
| 254111 | |
| 1202295 | |
| 102554 | |
| 23289 | |
| 988177 | |
| 784196 | |
| 466609 | |
| 200163 | |
| 430492 | |
| 119524 | |
| 90959 | |
| 421332 | |
| 1077910 | |
| 460406 | |
| 284695 | |
| 842086 | |
| 320312 | |
| 559356 | |
| 164305 | |
| 236245 | |
| 902728 | |
| 947287 | |
| 983796 | |
| 1089049 | |
| 1274397 | |
| 1044496 | |
| 993764 | |
| 1150350 | |
| 728049 | |
| 92016 | |
| 506621 | |
| 309452 | |
| 471861 | |
| 171836 | |
| 599253 | |
| 533660 | |
| 301692 | |
| 696449 | |
| 7334 | |
| 482470 | |
| 838215 | |
| 310466 | |
| 685800 | |
| 865661 | |
| 83230 | |
| 691973 | |
| 942384 | |
| 419844 | |
| 530387 | |
| 1089484 | |
| 1283342 | |
| 786252 | |
| 425638 | |
| 61251 | |
| 19952 | |
| 1208844 | |
| 200016 | |
| 1102927 | |
| 730474 | |
| 1060471 | |
| 234078 | |
| 1001527 | |
| 1168818 | |
| 244517 | |
| 1160730 | |
| 93590 | |
| 1233002 | |
| 771806 | |
| 1093893 | |
| 576589 | |
| 504848 | |
| 1296101 | |
| 118832 | |
| 686854 | |
| 1250285 | |
| 1181569 | |
| 762533 | |
| 283287 | |
| 306052 | |
| 901626 | |
| 964667 | |
| 1208084 | |
| 500422 | |
| 356040 | |
| 77645 | |
| 1140112 | |
| 1257377 | |
| 1054407 | |
| 136187 | |
| 456710 | |
| 242905 | |
| 384990 | |
| 265836 | |
| 257708 | |
| 1217188 | |
| 1034341 | |
| 817444 | |
| 6347 | |
| 28323 | |
| 53763 | |
| 555200 | |
| 37219 | |
| 9956 | |
| 351016 | |
| 717235 | |
| 42769 | |
| 1149437 | |
| 1091002 | |
| 261092 | |
| 547981 | |
| 1194857 | |
| 539214 | |
| 254415 | |
| 111306 | |
| 1289085 | |
| 417427 | |
| 599598 | |
| 885157 | |
| 896830 | |
| 229057 | |
| 263642 | |
| 920005 | |
| 744473 | |
| 1113417 | |
| 241751 | |
| 983355 | |
| 57070 | |
| 166038 | |
| 1286226 | |
| 1182555 | |
| 409455 | |
| 767493 | |
| 954054 | |
| 1240348 | |
| 659204 | |
| 1120038 | |
| 762234 | |
| 460167 | |
| 714571 | |
| 405453 | |
| 1088160 | |
| 853562 | |
| 1043880 | |
| 298862 | |
| 689391 | |
| 669383 | |
| 729015 | |
| 505781 | |
| 1115268 | |
| 490541 | |
| 950250 | |
| 128677 | |
| 490374 | |
| 909048 | |
| 864776 | |
| 1153992 | |
| 298764 | |
| 177525 | |
| 1038436 | |
| 606070 | |
| 530452 | |
| 1044091 | |
| 169331 | |
| 928841 | |
| 166818 | |
| 777780 | |
| 675597 | |
| 1244790 | |
| 112085 | |
| 706814 | |
| 1230443 | |
| 617 | |
| 535131 | |
| 588208 | |
| 1057457 | |
| 768050 | |
| 240667 | |
| 1036418 | |
| 381279 | |
| 368545 | |
| 856707 | |
| 452522 | |
| 1047834 | |
| 1043664 | |
| 767707 | |
| 109193 | |
| 629553 | |
| 1204464 | |
| 499376 | |
| 483237 | |
| 1051472 | |
| 924557 | |
| 431300 | |
| 767323 | |
| 711335 | |
| 506281 | |
| 1118143 | |
| 443535 | |
| 247354 | |
| 983841 | |
| 365603 | |
| 731614 | |
| 395042 | |
| 782100 | |
| 84532 | |
| 792324 | |
| 139262 | |
| 990530 | |
| 761963 | |
| 167856 | |
| 467842 | |
| 191688 | |
| 506024 | |
| 1135728 | |
| 363024 | |
| 303148 | |
| 1260372 | |
| 1184930 | |
| 687374 | |
| 374865 | |
| 701401 | |
| 652242 | |
| 837058 | |
| 980509 | |
| 117020 | |
| 269067 | |
| 724958 | |
| 1157359 | |
| 1109820 | |
| 597394 | |
| 1176614 | |
| 595457 | |
| 311125 | |
| 1050269 | |
| 51530 | |
| 796195 | |
| 124700 | |
| 109935 | |
| 529053 | |
| 1068296 | |
| 958983 | |
| 618864 | |
| 776139 | |
| 976981 | |
| 1253491 | |
| 815716 | |
| 329741 | |
| 496110 | |
| 84789 | |
| 1026662 | |
| 928119 | |
| 957112 | |
| 150844 | |
| 1211850 | |
| 831973 | |
| 740620 | |
| 493327 | |
| 325969 | |
| 1217294 | |
| 713598 | |
| 120111 | |
| 235438 | |
| 501582 | |
| 1091670 | |
| 525312 | |
| 906795 | |
| 358691 | |
| 1147403 | |
| 605914 | |
| 561676 | |
| 596270 | |
| 617127 | |
| 1036328 | |
| 418697 | |
| 644227 | |
| 175726 | |
| 1081869 | |
| 1167386 | |
| 131037 | |
| 746315 | |
| 464649 | |
| 87013 | |
| 770777 | |
| 653090 | |
| 82177 | |
| 349410 | |
| 756452 | |
| 278712 | |
| 932362 | |
| 788616 | |
| 261268 | |
| 1044776 | |
| 620048 | |
| 483249 | |
| 375032 | |
| 154684 | |
| 357109 | |
| 17407 | |
| 596710 | |
| 431111 | |
| 196712 | |
| 257861 | |
| 1004892 | |
| 508535 | |
| 507263 | |
| 71994 | |
| 1241636 | |
| 718095 | |
| 340916 | |
| 435054 | |
| 408558 | |
| 409444 | |
| 1108353 | |
| 488280 | |
| 753148 | |
| 599554 | |
| 1080223 | |
| 762579 | |
| 780505 | |
| 34600 | |
| 868190 | |
| 889503 | |
| 715319 | |
| 944903 | |
| 300621 | |
| 995078 | |
| 699048 | |
| 599765 | |
| 912338 | |
| 386167 | |
| 660548 | |
| 883395 | |
| 1276415 | |
| 534809 | |
| 379154 | |
| 760498 | |
| 174818 | |
| 494544 | |
| 923675 | |
| 24413 | |
| 420799 | |
| 983872 | |
| 227375 | |
| 412759 | |
| 628722 | |
| 767916 | |
| 57081 | |
| 844607 | |
| 325078 | |
| 9217 | |
| 144067 | |
| 697809 | |
| 601650 | |
| 802375 | |
| 692157 | |
| 1053731 | |
| 1244517 | |
| 1276645 | |
| 324021 | |
| 1196804 | |
| 504580 | |
| 102174 | |
| 422174 | |
| 880720 | |
| 1019833 | |
| 824540 | |
| 519076 | |
| 640544 | |
| 1231145 | |
| 1013972 | |
| 994826 | |
| 1255060 | |
| 1248151 | |
| 155533 | |
| 1080564 | |
| 504171 | |
| 868037 | |
| 230602 | |
| 1136519 | |
| 720198 | |
| 548297 | |
| 688001 | |
| 780252 | |
| 61657 | |
| 496665 | |
| 111893 | |
| 707749 | |
| 917787 | |
| 935144 | |
| 70393 | |
| 167238 | |
| 471705 | |
| 257614 | |
| 338669 | |
| 835529 | |
| 224052 | |
| 76894 | |
| 378345 | |
| 340164 | |
| 450143 | |
| 270569 | |
| 569664 | |
| 839157 | |
| 219319 | |
| 886235 | |
| 1071029 | |
| 1075181 | |
| 1215327 | |
| 937738 | |
| 940606 | |
| 1223674 | |
| 750600 | |
| 677800 | |
| 111128 | |
| 1081798 | |
| 1190009 | |
| 450168 | |
| 1285930 | |
| 0 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment