// yukicoder: No.406 鴨等間隔の法則 // 2019.4.16 bal4u #include #include #define MAX 5000002 char notPrime[MAX + 2] = { 1,1,0,0,1 }; // zero: if prime void sieve(int max) { int i, j, b; b = (int)sqrt((double)max); for (i = 3; i <= b; i += 2) { if (!notPrime[i]) { for (j = i * i; j <= max; j += i) notPrime[j] = 1; } } } #define RANGE 10000 long long tbl[505][2] = { {0, 0}, {1228,5736394}, {2261,21171189}, {3244,45675862}, {4202,79170664}, {5132,121013306}, {6056,171848736}, {6934,228890416}, {7836,296488206}, {8712,370927312}, {9591,454396535}, {10452,544815054}, {11300,642361190}, {12158,749586244}, {13009,864482119}, {13847,986017445}, {14682,1115391664}, {15496,1249676488}, {16341,1397596537}, {17169,1550847683}, {17983,1709600811}, {18806,1878392366}, {19617,2052799923}, {20436,2237143102}, {21220,2421385276}, {22043,2623031149}, {22836,2825260460}, {23641,3038641893}, {24431,3255847669}, {25223,3481508699}, {25996,3709507112}, {26799,3954371769}, {27607,4208959127}, {28403,4467656213}, {29181,4728235703}, {29976,5002513512}, {30756,5279384844}, {31521,5558589577}, {32299,5850385909}, {33066,6145711712}, {33859,6458901529}, {34613,6764361103}, {35389,7086429797}, {36161,7414564287}, {36940,7753373170}, {37705,8093723583}, {38457,8435814137}, {39222,8791579374}, {40004,9162979208}, {40765,9532077299}, {41537,9914236193}, {42290,10294506868}, {43060,10691097202}, {43824,11092186116}, {44571,11491808989}, {45321,11900563181}, {46071,12316800851}, {46818,12738842358}, {47587,13180991083}, {48350,13627351484}, {49097,14071826343}, {49860,14533463862}, {50611,14995344483}, {51340,15450946376}, {52073,15916347209}, {52830,16404679970}, {53563,16884834921}, {54308,17380202288}, {55062,17889176420}, {55814,18404329914}, {56542,18910286310}, {57305,19448220645}, {58028,19965116920}, {58788,20516088662}, {59530,21061503170}, {60237,21588259023}, {60977,22146949833}, {61732,22724500916}, {62467,23294120341}, {63205,23873433067}, {63950,24465663436}, {64682,25054895046}, {65415,25652285581}, {66160,26266844424}, {66889,26875509717}, {67616,27489818804}, {68341,28109692653}, {69094,28761037052}, {69822,29398075550}, {70554,30045873872}, {71273,30689332263}, {72025,31369995681}, {72733,32017875925}, {73473,32702363907}, {74186,33369015916}, {74906,34049359800}, {75617,34728329601}, {76349,35434672611}, {77066,36133654012}, {77776,36833009472}, {78497,37550402021}, {79250,38307175232}, {79969,39036979343}, {80701,39787246769}, {81402,40512751710}, {82133,41276629125}, {82831,42013066533}, {83547,42775656981}, {84269,43551818387}, {84975,44317727437}, {85713,45125753693}, {86449,45939043061}, {87165,46737288747}, {87883,47545060013}, {88601,48359954121}, {89301,49161463645}, {90029,50002290949}, {90763,50857322923}, {91489,51710417935}, {92224,52581367530}, {92937,53433406129}, {93613,54247978153}, {94357,55151942211}, {95050,56000935130}, {95744,56858064010}, {96468,57759511222}, {97181,58654399057}, {97899,59562673235}, {98609,60467892783}, {99331,61395716183}, {100020,62287995770}, {100729,63213221261}, {101432,64137644484}, {102145,65082300453}, {102851,66024839999}, {103543,66955471631}, {104257,67922898251}, {104966,68890666706}, {105689,69884867901}, {106384,70847450774}, {107125,71881256645}, {107804,72835297770}, {108486,73800261878}, {109204,74823439624}, {109927,75860935735}, {110629,76875349477}, {111330,77895250782}, {112046,78944124462}, {112751,79984094035}, {113457,81032532937}, {114154,82074443254}, {114885,83174552715}, {115587,84238036221}, {116278,85291831550}, {116964,86344912342}, {117662,87423357962}, {118375,88532117557}, {119056,89597890448}, {119757,90701913605}, {120450,91800358762}, {121126,92878592186}, {121845,94032481433}, {122539,95153302905}, {123249,96307074511}, {123941,97438402703}, {124633,98576757975}, {125334,99736854912}, {126050,100929095376}, {126752,102105030430}, {127427,103242387749}, {128140,104450958702}, {128836,105637642134}, {129521,106812427039}, {130212,108004427026}, {130901,109199917323}, {131607,110431974855}, {132291,111632300729}, {132970,112830807268}, {133670,114073320386}, {134358,115301312590}, {135071,116581137845}, {135775,117851921689}, {136447,119071568441}, {137165,120381909889}, {137840,121620451716}, {138541,122913801663}, {139248,124225299762}, {139951,125536370799}, {140640,126828232636}, {141337,128142060783}, {142028,129451433480}, {142717,130764039557}, {143413,132096820083}, {144124,133465548884}, {144809,134791081475}, {145501,136136977175}, {146185,137474175075}, {146858,138796554296}, {147528,140119853674}, {148218,141489414870}, {148932,142913828920}, {149637,144327406493}, {150327,145717765397}, {151020,147121099848}, {151710,148525232918}, {152381,149897385937}, {153077,151327709761}, {153771,152760859961}, {154444,154157377456}, {155130,155587733704}, {155804,156999759088}, {156503,158471116895}, {157186,159915649010}, {157883,161396844759}, {158556,162833730070}, {159249,164320146627}, {159961,165854577431}, {160628,167298642258}, {161318,168799373802}, {161997,170283021419}, {162661,171740398595}, {163362,173286138414}, {164022,174747995306}, {164717,176294429247}, {165397,177814211635}, {166080,179347555626}, {166768,180899065884}, {167469,182486829961}, {168163,184065574547}, {168825,185578301631}, {169510,187150390018}, {170200,188740844660}, {170862,190273400906}, {171534,191835856658}, {172205,193402646833}, {172872,194966694834}, {173562,196591659714}, {174253,198225885763}, {174915,199798140173}, {175620,201479578708}, {176301,203110644371}, {176961,204697936469}, {177653,206369146569}, {178325,207998730139}, {178982,209598483974}, {179683,211312414613}, {180370,212999039432}, {181038,214645613464}, {181710,216308794360}, {182397,218016021091}, {183071,219697708193}, {183747,221391071189}, {184422,223088646492}, {185119,224848583881}, {185791,226552054205}, {186461,228257241323}, {187133,229974210047}, {187811,231713234103}, {188510,233513149116}, {189203,235304510773}, {189879,237058773599}, {190532,238759857916}, {191213,240540618951}, {191885,242304623831}, {192566,244098978642}, {193255,245921375955}, {193950,247766614888}, {194612,249530836804}, {195277,251309795385}, {195958,253138317634}, {196644,254987085882}, {197323,256823807179}, {198018,258710786800}, {198663,260468459323}, {199320,262265360936}, {199992,264109919010}, {200663,265958531443}, {201348,267852513842}, {202014,269700656886}, {202677,271547053849}, {203361,273458891713}, {204051,275394381825}, {204746,277350769856}, {205413,279234986387}, {206117,281230805481}, {206788,283139850040}, {207442,285006986776}, {208115,286935084861}, {208768,288812427414}, {209446,290768444866}, {210108,292684958372}, {210789,294663286913}, {211452,296595987708}, {212123,298558620103}, {212803,300554476085}, {213452,302465859298}, {214104,304392467168}, {214798,306450148766}, {215457,308410691391}, {216128,310413497778}, {216815,312471072263}, {217485,314484412015}, {218144,316471223350}, {218807,318476761555}, {219464,320470709142}, {220135,322513849671}, {220792,324520973184}, {221456,326556144108}, {222151,328693223505}, {222837,330809580765}, {223491,332833640337}, {224167,334932681313}, {224844,337041587392}, {225510,339122860876}, {226176,341210777884}, {226834,343280247428}, {227511,345416120935}, {228179,347530369337}, {228842,349635301708}, {229533,351836156573}, {230208,353992813412}, {230894,356191388908}, {231568,358358249162}, {232240,360525441686}, {232927,362747913057}, {233576,364853955188}, {234238,367008768698}, {234915,369219134093}, {235581,371400281195}, {236251,373601253351}, {236899,375736342229}, {237572,377960682220}, {238232,380148556614}, {238909,382399618815}, {239554,384550763340}, {240229,386808600813}, {240852,388898719270}, {241540,391213899630}, {242207,393465050425}, {242876,395729648494}, {243538,397977139118}, {244215,400282292893}, {244881,402556594319}, {245553,404858175151}, {246238,407211199514}, {246908,409519353578}, {247554,411751250114}, {248208,414017402208}, {248845,416230966331}, {249481,418447415489}, {250149,420782056779}, {250800,423063851578}, {251463,425394272411}, {252093,427615015631}, {252756,429958648536}, {253411,432280637141}, {254079,434655434417}, {254749,437044043415}, {255389,439332020573}, {256056,441723179790}, {256725,444128260161}, {257417,446622971393}, {258087,449044984945}, {258773,451531707201}, {259425,453901726847}, {260063,456227195827}, {260713,458603010947}, {261375,461029271431}, {262077,463609198607}, {262715,465960290649}, {263396,468476582950}, {264051,470903326797}, {264722,473396155798}, {265409,475955313733}, {266067,478412919877}, {266716,480843495728}, {267383,483348018297}, {268015,485727595823}, {268670,488200274032}, {269329,490694569445}, {269986,493187952848}, {270642,495684022880}, {271324,498285816594}, {271998,500863849642}, {272644,503341273528}, {273321,505944316357}, {273971,508450118011}, {274617,510946885327}, {275268,513469528244}, {275929,516037505633}, {276610,518689939918}, {277261,521232198657}, {277919,523808279387}, {278594,526457723238}, {279242,529007619546}, {279920,531682316040}, {280563,534225380181}, {281201,536755102791}, {281869,539410380853}, {282503,541936864523}, {283145,544501644259}, {283805,547144926769}, {284463,549786750863}, {285131,552475436129}, {285808,555207138826}, {286489,557961747891}, {287132,560569129414}, {287785,563223579819}, {288455,565953844897}, {289108,568621365098}, {289773,571344516341}, {290436,574066225976}, {291064,576650415916}, {291716,579339928458}, {292348,581953321640}, {293009,584693196537}, {293671,587443798745}, {294342,590238403238}, {294993,592956369183}, {295666,595772903134}, {296313,598487027811}, {296983,601304350063}, {297627,604018781441}, {298290,606819902238}, {298918,609479465308}, {299582,612298118390}, {300242,615106353784}, {300886,617852954998}, {301542,620657328454}, {302174,623365435754}, {302823,626152906523}, {303485,629002776743}, {304151,631876630481}, {304792,634649068196}, {305448,637492887946}, {306083,640251966747}, {306723,643039133261}, {307376,645889463930}, {308037,648781273863}, {308699,651684101047}, {309334,654474931930}, {309975,657298501885}, {310654,660296284262}, {311337,663318596819}, {311993,666228037955}, {312665,669215051745}, {313320,672133077942}, {313980,675079985628}, {314626,677970845128}, {315309,681034104231}, {315947,683901919557}, {316600,686843627982}, {317238,689724236830}, {317884,692647431508}, {318515,695509027495}, {319163,698454128773}, {319822,701455802406}, {320495,704528040289}, {321145,707501891301}, {321785,710436285201}, {322440,713445920554}, {323102,716494466158}, {323758,719521918188}, {324403,722505066015}, {325054,725522485480}, {325705,728546440791}, {326321,731413933199}, {326986,734516156846}, {327652,737629753782}, {328319,740754629567}, {328963,743778235403}, {329615,746845846437}, {330268,749924791660}, {330911,752962953359}, {331574,756102153392}, {332218,759157891568}, {332860,762210648918}, {333515,765331720301}, {334143,768330436293}, {334800,771474159582}, {335438,774533452862}, {336095,777690271805}, {336750,780844143802}, {337381,783888697601}, {338059,787166873551}, {338693,790238649867}, {339338,793370075946}, {340007,796624764265}, {340643,799725258475}, {341312,802993312680}, {341991,806316986091}, {342642,809510088782}, {343276,812626213776}, {343929,815842184881}, {344584,819074602964}, {345234,822288858552}, {345874,825459979508}, {346557,828851008725}, {347218,832139611488}, {347871,835394918645}, {348512,838596693106}}; #if 1 int main() { int i, k, N, L, max; long long ans, s; scanf("%d%d", &N, &L); max = L / (N - 1); sieve(max); ans = 0, N--, L++; if (2 <= max) ans = L - (N << 1); k = (int)tbl[max/RANGE][0], s = tbl[max/RANGE][1]; for (i = max/RANGE*RANGE+1; i <= max; i += 2) if (!notPrime[i]) k++, s += i; if (k) ans += (long long)k*L - (long long)N*s; printf("%lld\n", ans); return 0; } #else int main() { int i, k, sz; long long s; sieve(MAX); printf("int tbl[502][2] = {\n"); sz = 1; k = 0, s = 0; for (i = 3; i <= MAX; i += 2) { if (i % RANGE == 1) { printf("{%d,%lld}, ", k, s); sz++; if (sz % 5 == 0) printf("\n"); } if (!notPrime[i]) k++, s += i; } printf("};\n"); printf("sz=%d\n", sz); return 0; } #endif