<p>There is only one character <code>&#39;A&#39;</code> on the screen of a notepad. You can perform one of two operations on this notepad for each step:</p>

<ul>
	<li>Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).</li>
	<li>Paste: You can paste the characters which are copied last time.</li>
</ul>

<p>Given an integer <code>n</code>, return <em>the minimum number of operations to get the character</em> <code>&#39;A&#39;</code> <em>exactly</em> <code>n</code> <em>times on the screen</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> Initially, we have one character &#39;A&#39;.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get &#39;AA&#39;.
In step 3, we use Paste operation to get &#39;AAA&#39;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
</ul>

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