#include <vector> #include <string> #include <iostream> #include <iomanip> #include <cmath> using namespace std; class PrimeTable { public: PrimeTable(unsigned int count); ~PrimeTable() { delete[] table; } bool isPrime(long long n); int next(int p); private: bool * table; int count; }; PrimeTable::PrimeTable(unsigned int count) :count(count) { table = new bool[count+1]; for(unsigned int i = 0; i <= count; ++i) table[i] = true; table[0] = table[1] = false; int last = sqrt(count)+1; for(int i = 2; i <= last; ++i) { if (table[i] == false) continue; for(unsigned int j = 2*i; j <= count; j += i) table[j] = false; } } bool PrimeTable::isPrime(long long N) { if (N <= count) return table[N]; int last = sqrt(N)+1; for(int i = 2; i <= last; i++) { if (table[i] == false) continue; if (N%i == 0) return false; } return true; } int PrimeTable::next(int p) { if (p < count) { for(++p; p <= count; ++p) if (table[p]) return p; } return -1; } int CountDivs(unsigned int N) { static PrimeTable t(10000); int count = 1; unsigned int M = N; while(N > 1) { for(int p = 2; p > 0 && t.isPrime(p) && p < sqrt(N) + 1; p = t.next(p)) { int ex = 0; while(N%p == 0) { // cout << "Found " << p << endl; ++ex; N /= p; } count *= ex+1; } if (M == N) { count *= 2; N = 1; } // prime else M = N; } return count; } int main(int argc, const char * argv[]) { for(int N = 1; N < 1000; ++N) cout << setw(5) << N << ": " << setw(4) << CountDivs(N) << endl; }
Standard input is empty
1: 1 2: 2 3: 2 4: 3 5: 2 6: 4 7: 2 8: 4 9: 3 10: 4 11: 2 12: 6 13: 2 14: 4 15: 4 16: 5 17: 2 18: 6 19: 2 20: 6 21: 4 22: 4 23: 2 24: 8 25: 3 26: 4 27: 4 28: 6 29: 2 30: 8 31: 2 32: 6 33: 4 34: 4 35: 4 36: 9 37: 2 38: 4 39: 4 40: 8 41: 2 42: 8 43: 2 44: 6 45: 6 46: 4 47: 2 48: 10 49: 3 50: 6 51: 4 52: 6 53: 2 54: 8 55: 4 56: 8 57: 4 58: 4 59: 2 60: 12 61: 2 62: 4 63: 6 64: 7 65: 4 66: 8 67: 2 68: 6 69: 4 70: 8 71: 2 72: 12 73: 2 74: 4 75: 6 76: 6 77: 4 78: 8 79: 2 80: 10 81: 5 82: 4 83: 2 84: 12 85: 4 86: 4 87: 4 88: 8 89: 2 90: 12 91: 4 92: 6 93: 4 94: 4 95: 4 96: 12 97: 2 98: 6 99: 6 100: 9 101: 2 102: 8 103: 2 104: 8 105: 8 106: 4 107: 2 108: 12 109: 2 110: 8 111: 4 112: 10 113: 2 114: 8 115: 4 116: 6 117: 6 118: 4 119: 4 120: 16 121: 3 122: 4 123: 4 124: 6 125: 4 126: 12 127: 2 128: 8 129: 4 130: 8 131: 2 132: 12 133: 4 134: 4 135: 8 136: 8 137: 2 138: 8 139: 2 140: 12 141: 4 142: 4 143: 4 144: 15 145: 4 146: 4 147: 6 148: 6 149: 2 150: 12 151: 2 152: 8 153: 6 154: 8 155: 4 156: 12 157: 2 158: 4 159: 4 160: 12 161: 4 162: 10 163: 2 164: 6 165: 8 166: 4 167: 2 168: 16 169: 3 170: 8 171: 6 172: 6 173: 2 174: 8 175: 6 176: 10 177: 4 178: 4 179: 2 180: 18 181: 2 182: 8 183: 4 184: 8 185: 4 186: 8 187: 4 188: 6 189: 8 190: 8 191: 2 192: 14 193: 2 194: 4 195: 8 196: 9 197: 2 198: 12 199: 2 200: 12 201: 4 202: 4 203: 4 204: 12 205: 4 206: 4 207: 6 208: 10 209: 4 210: 16 211: 2 212: 6 213: 4 214: 4 215: 4 216: 16 217: 4 218: 4 219: 4 220: 12 221: 4 222: 8 223: 2 224: 12 225: 9 226: 4 227: 2 228: 12 229: 2 230: 8 231: 8 232: 8 233: 2 234: 12 235: 4 236: 6 237: 4 238: 8 239: 2 240: 20 241: 2 242: 6 243: 6 244: 6 245: 6 246: 8 247: 4 248: 8 249: 4 250: 8 251: 2 252: 18 253: 4 254: 4 255: 8 256: 9 257: 2 258: 8 259: 4 260: 12 261: 6 262: 4 263: 2 264: 16 265: 4 266: 8 267: 4 268: 6 269: 2 270: 16 271: 2 272: 10 273: 8 274: 4 275: 6 276: 12 277: 2 278: 4 279: 6 280: 16 281: 2 282: 8 283: 2 284: 6 285: 8 286: 8 287: 4 288: 18 289: 3 290: 8 291: 4 292: 6 293: 2 294: 12 295: 4 296: 8 297: 8 298: 4 299: 4 300: 18 301: 4 302: 4 303: 4 304: 10 305: 4 306: 12 307: 2 308: 12 309: 4 310: 8 311: 2 312: 16 313: 2 314: 4 315: 12 316: 6 317: 2 318: 8 319: 4 320: 14 321: 4 322: 8 323: 4 324: 15 325: 6 326: 4 327: 4 328: 8 329: 4 330: 16 331: 2 332: 6 333: 6 334: 4 335: 4 336: 20 337: 2 338: 6 339: 4 340: 12 341: 4 342: 12 343: 4 344: 8 345: 8 346: 4 347: 2 348: 12 349: 2 350: 12 351: 8 352: 12 353: 2 354: 8 355: 4 356: 6 357: 8 358: 4 359: 2 360: 24 361: 3 362: 4 363: 6 364: 12 365: 4 366: 8 367: 2 368: 10 369: 6 370: 8 371: 4 372: 12 373: 2 374: 8 375: 8 376: 8 377: 4 378: 16 379: 2 380: 12 381: 4 382: 4 383: 2 384: 16 385: 8 386: 4 387: 6 388: 6 389: 2 390: 16 391: 4 392: 12 393: 4 394: 4 395: 4 396: 18 397: 2 398: 4 399: 8 400: 15 401: 2 402: 8 403: 4 404: 6 405: 10 406: 8 407: 4 408: 16 409: 2 410: 8 411: 4 412: 6 413: 4 414: 12 415: 4 416: 12 417: 4 418: 8 419: 2 420: 24 421: 2 422: 4 423: 6 424: 8 425: 6 426: 8 427: 4 428: 6 429: 8 430: 8 431: 2 432: 20 433: 2 434: 8 435: 8 436: 6 437: 4 438: 8 439: 2 440: 16 441: 9 442: 8 443: 2 444: 12 445: 4 446: 4 447: 4 448: 14 449: 2 450: 18 451: 4 452: 6 453: 4 454: 4 455: 8 456: 16 457: 2 458: 4 459: 8 460: 12 461: 2 462: 16 463: 2 464: 10 465: 8 466: 4 467: 2 468: 18 469: 4 470: 8 471: 4 472: 8 473: 4 474: 8 475: 6 476: 12 477: 6 478: 4 479: 2 480: 24 481: 4 482: 4 483: 8 484: 9 485: 4 486: 12 487: 2 488: 8 489: 4 490: 12 491: 2 492: 12 493: 4 494: 8 495: 12 496: 10 497: 4 498: 8 499: 2 500: 12 501: 4 502: 4 503: 2 504: 24 505: 4 506: 8 507: 6 508: 6 509: 2 510: 16 511: 4 512: 10 513: 8 514: 4 515: 4 516: 12 517: 4 518: 8 519: 4 520: 16 521: 2 522: 12 523: 2 524: 6 525: 12 526: 4 527: 4 528: 20 529: 3 530: 8 531: 6 532: 12 533: 4 534: 8 535: 4 536: 8 537: 4 538: 4 539: 6 540: 24 541: 2 542: 4 543: 4 544: 12 545: 4 546: 16 547: 2 548: 6 549: 6 550: 12 551: 4 552: 16 553: 4 554: 4 555: 8 556: 6 557: 2 558: 12 559: 4 560: 20 561: 8 562: 4 563: 2 564: 12 565: 4 566: 4 567: 10 568: 8 569: 2 570: 16 571: 2 572: 12 573: 4 574: 8 575: 6 576: 21 577: 2 578: 6 579: 4 580: 12 581: 4 582: 8 583: 4 584: 8 585: 12 586: 4 587: 2 588: 18 589: 4 590: 8 591: 4 592: 10 593: 2 594: 16 595: 8 596: 6 597: 4 598: 8 599: 2 600: 24 601: 2 602: 8 603: 6 604: 6 605: 6 606: 8 607: 2 608: 12 609: 8 610: 8 611: 4 612: 18 613: 2 614: 4 615: 8 616: 16 617: 2 618: 8 619: 2 620: 12 621: 8 622: 4 623: 4 624: 20 625: 5 626: 4 627: 8 628: 6 629: 4 630: 24 631: 2 632: 8 633: 4 634: 4 635: 4 636: 12 637: 6 638: 8 639: 6 640: 16 641: 2 642: 8 643: 2 644: 12 645: 8 646: 8 647: 2 648: 20 649: 4 650: 12 651: 8 652: 6 653: 2 654: 8 655: 4 656: 10 657: 6 658: 8 659: 2 660: 24 661: 2 662: 4 663: 8 664: 8 665: 8 666: 12 667: 4 668: 6 669: 4 670: 8 671: 4 672: 24 673: 2 674: 4 675: 12 676: 9 677: 2 678: 8 679: 4 680: 16 681: 4 682: 8 683: 2 684: 18 685: 4 686: 8 687: 4 688: 10 689: 4 690: 16 691: 2 692: 6 693: 12 694: 4 695: 4 696: 16 697: 4 698: 4 699: 4 700: 18 701: 2 702: 16 703: 4 704: 14 705: 8 706: 4 707: 4 708: 12 709: 2 710: 8 711: 6 712: 8 713: 4 714: 16 715: 8 716: 6 717: 4 718: 4 719: 2 720: 30 721: 4 722: 6 723: 4 724: 6 725: 6 726: 12 727: 2 728: 16 729: 7 730: 8 731: 4 732: 12 733: 2 734: 4 735: 12 736: 12 737: 4 738: 12 739: 2 740: 12 741: 8 742: 8 743: 2 744: 16 745: 4 746: 4 747: 6 748: 12 749: 4 750: 16 751: 2 752: 10 753: 4 754: 8 755: 4 756: 24 757: 2 758: 4 759: 8 760: 16 761: 2 762: 8 763: 4 764: 6 765: 12 766: 4 767: 4 768: 18 769: 2 770: 16 771: 4 772: 6 773: 2 774: 12 775: 6 776: 8 777: 8 778: 4 779: 4 780: 24 781: 4 782: 8 783: 8 784: 15 785: 4 786: 8 787: 2 788: 6 789: 4 790: 8 791: 4 792: 24 793: 4 794: 4 795: 8 796: 6 797: 2 798: 16 799: 4 800: 18 801: 6 802: 4 803: 4 804: 12 805: 8 806: 8 807: 4 808: 8 809: 2 810: 20 811: 2 812: 12 813: 4 814: 8 815: 4 816: 20 817: 4 818: 4 819: 12 820: 12 821: 2 822: 8 823: 2 824: 8 825: 12 826: 8 827: 2 828: 18 829: 2 830: 8 831: 4 832: 14 833: 6 834: 8 835: 4 836: 12 837: 8 838: 4 839: 2 840: 32 841: 3 842: 4 843: 4 844: 6 845: 6 846: 12 847: 6 848: 10 849: 4 850: 12 851: 4 852: 12 853: 2 854: 8 855: 12 856: 8 857: 2 858: 16 859: 2 860: 12 861: 8 862: 4 863: 2 864: 24 865: 4 866: 4 867: 6 868: 12 869: 4 870: 16 871: 4 872: 8 873: 6 874: 8 875: 8 876: 12 877: 2 878: 4 879: 4 880: 20 881: 2 882: 18 883: 2 884: 12 885: 8 886: 4 887: 2 888: 16 889: 4 890: 8 891: 10 892: 6 893: 4 894: 8 895: 4 896: 16 897: 8 898: 4 899: 4 900: 27 901: 4 902: 8 903: 8 904: 8 905: 4 906: 8 907: 2 908: 6 909: 6 910: 16 911: 2 912: 20 913: 4 914: 4 915: 8 916: 6 917: 4 918: 16 919: 2 920: 16 921: 4 922: 4 923: 4 924: 24 925: 6 926: 4 927: 6 928: 12 929: 2 930: 16 931: 6 932: 6 933: 4 934: 4 935: 8 936: 24 937: 2 938: 8 939: 4 940: 12 941: 2 942: 8 943: 4 944: 10 945: 16 946: 8 947: 2 948: 12 949: 4 950: 12 951: 4 952: 16 953: 2 954: 12 955: 4 956: 6 957: 8 958: 4 959: 4 960: 28 961: 3 962: 8 963: 6 964: 6 965: 4 966: 16 967: 2 968: 12 969: 8 970: 8 971: 2 972: 18 973: 4 974: 4 975: 12 976: 10 977: 2 978: 8 979: 4 980: 18 981: 6 982: 4 983: 2 984: 16 985: 4 986: 8 987: 8 988: 12 989: 4 990: 24 991: 2 992: 12 993: 4 994: 8 995: 4 996: 12 997: 2 998: 4 999: 8