# your code goes here import time import sys import functools from math import sqrt #print(f' sys.getrecursionlimit()={sys.getrecursionlimit()}') i=0 sys.setrecursionlimit(10000) @functools.lru_cache() def f(x): global i i +=1 if i%500==0: print(i) if x <=1: return 0 return 1 + min([ f(m + x // m - 2) for m in range(1,int(sqrt(x))+1) if x%m==0]) x = 2000 t0 = time.clock() print( f(x)) t1 = time.clock() print (t1-t0, ' i=', i)
1000000
500 1000 1500 2000 2500 3000 3500 4000 4500 5000 5500 6000 6500 7000 7500 8000 8500 9000 9500 10000 10500 11000 11500 12000 12500 13000 13500 14000 14500 15000 15500 16000 16500 17000 17500 18000 18500 19000 19500 20000 20500 21000 21500 22000 22500 23000 23500 24000 24500 25000 25500 26000 26500 27000 27500 28000 28500 29000 29500 30000 30500 31000 31500 32000 32500 33000 33500 34000 34500 35000 35500 36000 36500 37000 37500 38000 38500 39000 39500 40000 40500 41000 41500 42000 42500 43000 43500 44000 44500 45000 45500 46000 46500 47000 47500 48000 48500 49000 49500 50000 50500 51000 51500 52000 52500 53000 53500 54000 54500 55000 55500 56000 56500 57000 57500 58000 58500 59000 59500 60000 60500 61000 61500 62000 62500 63000 63500 64000 64500 65000 65500 66000 66500 67000 67500 68000 68500 69000 69500 70000 70500 71000 71500 72000 72500 73000 73500 74000 74500 75000 75500 76000 76500 77000 77500 78000 78500 79000 79500 80000 80500 81000 81500 82000 82500 83000 83500 84000 84500 85000 85500 86000 86500 87000 87500 88000 88500 89000 89500 90000 90500 91000 91500 92000 92500 93000 93500 94000 94500 95000 95500 96000 96500 97000 97500 98000 98500 99000 99500 100000 100500 101000 101500 102000 102500 103000 103500 104000 104500 105000 105500 106000 106500 107000 107500 108000 108500 109000 109500 110000 110500 111000 111500 112000 112500 113000 113500 114000 114500 115000 115500 116000 116500 117000 117500 118000 118500 119000 119500 120000 120500 121000 121500 122000 122500 123000 123500 124000 124500 125000 125500 126000 126500 127000 127500 128000 128500 129000 129500 130000 130500 131000 131500 132000 132500 133000 133500 134000 134500 135000 135500 136000 136500 137000 137500 138000 138500 139000 139500 140000 140500 141000 141500 142000 142500 143000 143500 144000 144500 145000 145500 146000 146500 147000 147500 148000 148500 149000 149500 150000 150500 151000 151500 152000 152500 153000 153500 154000 154500 155000 155500 156000 156500 157000 157500 158000 158500 159000 159500 160000 160500 161000 161500 162000 162500 163000 163500 164000 164500 165000 165500 166000 166500 167000 167500 168000 168500 169000 169500 170000 170500 171000 171500 172000 172500 173000 173500 174000 174500 175000 175500 176000 176500 177000 177500 178000 178500 179000 179500 180000 180500 181000 181500 182000 182500 183000 183500 184000 184500 185000 185500 186000 186500 187000 187500 188000 188500 189000 189500 190000 190500 191000 191500 192000 192500 193000 193500 194000 194500 195000 195500 196000 196500 197000 197500 198000 198500 199000 199500 200000 200500 201000 201500 202000 202500 203000 203500 204000 204500 205000 205500 206000 206500 207000 207500 208000 208500 209000 209500 210000 210500 211000 211500 212000 212500 213000 213500 214000 214500 215000 215500 216000 216500 217000 217500 218000 218500 219000 219500 220000 220500 221000 221500 222000 222500 223000 223500 224000 224500 225000 225500 226000 226500 227000 227500 228000 228500 229000 229500 230000 230500 231000 231500 232000 232500 233000 233500 234000 234500 235000 235500 236000 236500 237000 237500 238000 238500 239000 239500 240000 240500 241000 241500 242000 242500 243000 243500 244000 244500 245000 245500 246000 246500 247000 247500 248000 248500 249000 249500 250000 250500 251000 251500 252000 252500 253000 253500 254000 254500 255000 255500 256000 256500 257000 257500 258000 258500 259000 259500 260000 260500 261000 261500 262000 262500 263000 263500 264000 264500 265000 265500 266000 266500 267000 267500 268000 268500 269000 269500 270000 270500 271000 271500 272000 272500 273000 273500 274000 274500 275000 275500 276000 276500 277000 277500 278000 278500 279000 279500 280000 280500 281000 281500 282000 282500 283000 283500 284000 284500 285000 285500 286000 286500 287000 287500 288000 288500 289000 289500 290000 290500 291000 291500 292000 292500 293000 293500 294000 294500 295000 295500 296000 296500 297000 297500 298000 298500 299000 299500 300000 300500 301000 301500 302000 302500 303000 303500 304000 304500 305000 305500 306000 306500 307000 307500 308000 308500 309000 309500 310000 310500 311000 311500 312000 312500 313000 313500 314000 314500 315000 315500 316000 316500 317000 317500 318000 318500 319000 319500 320000 320500 321000 321500 322000 322500 323000 323500 324000 324500 325000 325500 326000 326500 327000 327500 328000 328500 329000 329500 330000 330500 331000 331500 332000 332500 333000 333500 334000 334500 335000 335500 336000 336500 337000 337500 338000 338500 339000 339500 340000 340500 341000 341500 342000 342500 343000 343500 344000 344500 345000 345500 346000 346500 347000 347500 348000 348500 349000 349500 350000 350500 351000 351500 352000 352500 353000 353500 354000 354500 355000 355500 356000 356500 357000 357500 358000 358500 359000 359500 360000 360500 361000 361500 362000 362500 363000 363500 364000 364500 365000 365500 366000 366500 367000 367500 368000 368500 369000 369500 370000 370500 371000 371500 372000 372500 373000 373500 374000 374500 375000 375500 376000 376500 377000 377500 378000 378500 379000 379500 380000 380500 381000 381500 382000 382500 383000 383500 384000 384500 385000 385500 386000 386500 387000 387500 388000 388500 389000 389500 390000 390500 391000 391500 392000 392500 393000 393500 394000 394500 395000 395500 396000 396500 397000 397500 398000 398500 399000 399500 400000 400500 401000 401500 402000 402500 403000 403500 404000 404500 405000 405500 406000 406500 407000 407500 408000 408500 409000 409500 410000 410500 411000 411500 412000 412500 413000 413500 414000 414500 415000 415500 416000 416500 417000 417500 418000 418500 419000 419500 420000 420500 421000 421500 422000 422500 423000 423500 424000 424500 425000 425500 426000 426500 427000 427500 428000 428500 429000 429500 430000 430500 431000 431500 432000 432500 433000 433500 434000 434500 435000 435500 436000 436500 437000 437500 438000 438500 439000 439500 440000 440500 441000 441500 442000 442500 443000 443500 444000 444500 445000 445500 446000 446500 447000 447500 448000 448500 449000 449500 450000 450500 451000 451500 452000 452500 453000 453500 454000 454500 455000 455500 456000 456500 457000 457500 458000 458500 459000 459500 460000 460500 461000 461500 462000 462500 463000 463500 464000 464500 465000 465500 466000 466500 467000 467500 468000 468500 469000 469500 470000 470500 471000 471500 472000 472500 473000 473500 474000 474500 475000 475500 476000 476500 477000 477500 478000 478500 479000 479500 480000 480500 481000 481500 482000 482500 483000 483500 484000 484500 485000 485500 486000 486500 487000 487500 488000 488500 489000 489500 490000 490500 491000 491500 492000 492500 493000 493500 494000 494500 495000 495500 496000 496500 497000 497500 498000 498500 499000 499500 500000 500500 501000 501500 502000 502500 503000 503500 504000 504500 505000 505500 506000 506500 507000 507500 508000 508500 509000 509500 510000 510500 511000 511500 512000 512500 513000 513500 514000 514500 515000 515500 516000 516500 517000 517500 518000 518500 519000 519500 520000 520500 521000 521500 522000 522500 523000 523500 524000 524500 525000 525500 526000 526500 527000 527500 528000 528500 529000 529500 530000 530500 531000 531500 532000 532500 533000 533500 534000 534500 535000 535500 536000 536500 537000 537500 538000 538500 539000 539500 540000 540500 541000 541500 542000 542500 543000 543500 544000 544500 545000 545500 546000 546500 547000 547500 548000 548500 549000 549500 550000 550500 551000 551500 552000 552500 553000 553500 554000 554500 555000 555500 556000 556500 557000 557500 558000 558500 559000 559500 560000 560500 561000 561500 562000 562500 563000 563500 564000 564500 565000 565500 566000 566500 567000 567500 568000 568500 569000 569500 570000 570500 571000 571500 572000 572500 573000 573500 574000 574500 575000 575500 576000 576500 577000 577500 578000 578500 579000 579500 580000 580500 581000 581500 582000 582500 583000 583500 584000 584500 585000 585500 586000 586500 587000 587500 588000 588500 589000 589500 590000 590500 591000 591500 592000 592500 593000 593500 594000 594500 595000 595500 596000 596500 597000 597500 598000 598500 599000 599500 600000 600500 601000 601500 602000 602500 603000 603500 604000 604500 605000 605500 606000 606500 607000 607500 608000 608500 609000 609500 610000 610500 611000 611500 612000 612500 613000 613500 614000 614500 615000 615500 616000 616500 617000 617500 618000 618500 619000 619500 620000 620500 621000 621500 622000 622500 623000 623500 624000 624500 625000 625500 626000 626500 627000 627500 628000 628500 629000 629500 630000 630500 631000 631500 632000 632500 633000 633500 634000 634500 635000 635500 636000 636500 637000 637500 638000 638500 639000 639500 640000 640500 641000 641500 642000 642500 643000 643500 644000 644500 645000 645500 646000 646500 647000 647500 648000 648500 649000 649500 650000 650500 651000 651500 652000 652500 653000 653500 654000 654500 655000 655500 656000 656500 657000 657500 658000 658500 659000 659500 660000 660500 661000 661500 662000 662500 663000 663500 664000 664500 665000 665500 666000 666500 667000 667500 668000 668500 669000 669500 670000 670500 671000 671500 672000 672500 673000 673500 674000 674500 675000 675500 676000 676500 677000 677500 678000 678500 679000 679500 680000 680500 681000 681500 682000 682500 683000 683500 684000 684500 685000 685500 686000 686500 687000 687500 688000 688500 689000 689500 690000 690500 691000 691500 692000 692500 693000 693500 694000 694500 695000 695500 696000 696500 697000 697500 698000 698500 699000 699500 700000 700500 701000 701500 702000 702500 703000 703500 704000 704500 705000 705500 706000 706500 707000 707500 708000 708500 709000 709500 710000 710500 711000 711500 712000 712500 713000 713500 714000 714500 715000 715500 716000 716500 717000 717500 718000 718500 719000 719500 720000 720500 721000 721500 722000 722500 723000 723500 724000 724500 725000 725500 726000 726500 727000 727500 728000 728500 729000 729500 730000 730500 731000 731500 732000 732500 733000 733500 734000 734500 735000 735500 736000 736500 737000 737500 738000 738500 739000 739500 740000 740500 741000 741500 742000 742500 743000 743500 744000 744500 745000 745500 746000 746500 747000 747500 748000 748500 749000 749500 750000 750500 751000 751500 752000 752500 753000 753500 754000 754500 755000 755500 756000 756500 757000 757500 758000 758500 759000 759500 760000 760500 761000 761500 762000 762500 763000 763500 764000 764500 765000 765500 766000 766500 767000 767500 768000 768500 769000 769500 770000 770500 771000 771500 772000 772500 773000 773500 774000 774500 775000 775500 776000 776500 777000 777500 778000 778500 779000 779500 780000 780500 781000 781500 782000 782500 783000 783500 784000 784500 785000 785500 786000 786500 787000 787500 788000 788500 789000 789500 790000 790500 791000 791500 792000 792500 793000 793500 794000 794500 795000 795500 796000 796500 797000 797500 798000 798500 799000 799500 800000 800500 801000 801500 802000 802500 803000 803500 804000 804500 805000 805500 806000 806500 807000 807500 808000 808500 809000 809500 810000 810500 811000 811500 812000 812500 813000 813500 814000 814500 815000 815500 816000 816500 817000 817500 818000 818500 819000 819500 820000 820500 821000 821500 822000 822500 823000 823500 824000 824500 825000 825500 826000 826500 827000 827500 828000 828500 829000 829500 830000 830500 831000 831500 832000 832500 833000 833500 834000 834500 835000 835500 836000 836500 837000 837500 838000 838500 839000 839500 840000 840500 841000 841500 842000 842500 843000 843500 844000 844500 845000 845500 846000 846500 847000 847500 848000 848500 849000 849500 850000 850500 851000 851500 852000 852500 853000 853500 854000 854500 855000 855500 856000 856500 857000 857500 858000 858500 859000 859500 860000 860500 861000 861500 862000 862500 863000 863500 864000 864500 865000 865500 866000 866500 867000 6 2.1930880000000004 i= 867080