#ifndef H_primes #define H_primes //--------------------------------------------------------------------------- // Pre-computed list of prime numbers, approx. 5% apart, with cheap div/modulo // computation. Suitable for efficient hash tables // // SPDX-License-Identifier: MIT // (c) 2020 Thomas Neumann // // Permission is hereby granted, free of charge, to any person obtaining a copy // of this software and associated documentation files (the "Software"), to // deal in the Software without restriction, including without limitation the // rights to use, copy, modify, merge, publish, distribute, sublicense, and/or // sell copies of the Software, and to permit persons to whom the Software is // furnished to do so, subject to the following conditions: // // The above copyright notice and this permission notice (including the next // paragraph) shall be included in all copies or substantial portions of the // Software. // // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER // DEALINGS IN THE SOFTWARE. //--------------------------------------------------------------------------- #include //--------------------------------------------------------------------------- namespace primes { //--------------------------------------------------------------------------- /// A pre-computed prime number, with efficient division and multiplication logic class Prime { private: /// A pre-computed number, i.e. Prime without the logic. /// We cannot use Prime in the primes array because the array is constexpr /// and Prime is not complete at the definition struct Number { uint64_t value, magic, shift; }; /// All pre-computed numbers static constexpr unsigned primeCount = 814; static constexpr Number primes[primeCount] = { {3ull, 12297829382473034411ull, 1}, {5ull, 14757395258967641293ull, 2}, {11ull, 3353953467947191203ull, 1}, {13ull, 5675921253449092805ull, 2}, {17ull, 17361641481138401521ull, 4}, {19ull, 15534100272597517151ull, 4}, {37ull, 15953940820505558155ull, 5}, {41ull, 14397458789236723213ull, 5}, {43ull, 13727809543225712831ull, 5}, {59ull, 10005013734893316131ull, 5}, {67ull, 17620770458468825425ull, 6}, {73ull, 8086243977516515777ull, 5}, {79ull, 7472098865300071541ull, 5}, {83ull, 3555998857582564167ull, 4}, {109ull, 10831115786398268839ull, 6}, {113ull, 10447713457676206225ull, 6}, {131ull, 281629680514649643ull, 1}, {139ull, 4246732448623781667ull, 5}, {149ull, 1980858424022502187ull, 4}, {157ull, 3759845925851628355ull, 5}, {163ull, 14485786757268850349ull, 7}, {173ull, 13648458042975853219ull, 7}, {191ull, 6181107961871263369ull, 6}, {211ull, 5595220951267352149ull, 6}, {227ull, 10401688288259130427ull, 7}, {241ull, 1224680104478642431ull, 4}, {257ull, 18374966859414961921ull, 8}, {269ull, 17555265735574889271ull, 8}, {283ull, 8343403679981705325ull, 7}, {307ull, 15382301247132394833ull, 8}, {331ull, 14266968226192281613ull, 8}, {349ull, 13531136054067751329ull, 8}, {373ull, 12660499954074115855ull, 8}, {397ull, 185861401246443845ull, 2}, {419ull, 5635282199128454909ull, 7}, {439ull, 10757099049816959485ull, 8}, {461ull, 5121872541073367911ull, 7}, {499ull, 591478767894494641ull, 4}, {523ull, 18058762840801702539ull, 9}, {557ull, 16956432613535530391ull, 9}, {587ull, 2011229336826935781ull, 6}, {617ull, 7653754429286296943ull, 8}, {647ull, 14597732559102458157ull, 9}, {691ull, 13668209791229074425ull, 9}, {727ull, 1623922449404967405ull, 6}, {769ull, 12281837406683082481ull, 9}, {809ull, 729661075845124415ull, 5}, {877ull, 673085302575491051ull, 5}, {941ull, 2509227674213414035ull, 7}, {997ull, 4736576211504157687ull, 8}, {1049ull, 18007117189207417403ull, 10}, {1103ull, 4281383937325154319ull, 8}, {1163ull, 8121008568993370961ull, 9}, {1223ull, 15445188823776435695ull, 10}, {1283ull, 7361444244535690123ull, 9}, {1367ull, 6909095073693701849ull, 9}, {1439ull, 13126800508324239649ull, 10}, {1523ull, 12402801005567026169ull, 10}, {1609ull, 2934969846407486149ull, 8}, {1693ull, 5578696376691843135ull, 9}, {1783ull, 5297102055939029965ull, 9}, {1871ull, 10095919792345580361ull, 10}, {1987ull, 9506525380713930979ull, 10}, {2087ull, 1131376732838918355ull, 7}, {2203ull, 1071803559434781029ull, 7}, {2333ull, 2024160515589217837ull, 8}, {2459ull, 15363534714500675767ull, 11}, {2591ull, 14580830514456642883ull, 11}, {2719ull, 6947210714041405243ull, 10}, {2857ull, 826455457275051665ull, 7}, {2999ull, 12597176346434532081ull, 11}, {3163ull, 11944018926006058081ull, 11}, {3323ull, 2842230805217962813ull, 9}, {3491ull, 10821808038658596881ull, 11}, {3671ull, 10291182746651365217ull, 11}, {3863ull, 9779687254195485817ull, 11}, {4091ull, 9234644796616270279ull, 11}, {4297ull, 17583864027441080619ull, 12}, {4513ull, 16742269826260652209ull, 12}, {4751ull, 15903570559022168685ull, 12}, {4987ull, 1893870656855682861ull, 9}, {5237ull, 7213849887904747319ull, 11}, {5501ull, 6867648039076015581ull, 11}, {5791ull, 3261865987131511113ull, 10}, {6079ull, 3107331128718305783ull, 10}, {6397ull, 11811452825686153419ull, 12}, {6733ull, 11222020455356352803ull, 12}, {7079ull, 5336761105093538877ull, 11}, {7433ull, 5082595434273800849ull, 11}, {7877ull, 9592213244371502275ull, 12}, {8269ull, 18274970063106620733ull, 13}, {8681ull, 17407640531255459837ull, 13}, {9127ull, 16556998734724295699ull, 13}, {9587ull, 15762566752042207869ull, 13}, {10067ull, 3752749762884390753ull, 11}, {10589ull, 14271010241933010373ull, 13}, {11117ull, 13593211068798115215ull, 13}, {11677ull, 12941314331748620951ull, 13}, {12263ull, 12322900387493162101ull, 13}, {12893ull, 732547348618575229ull, 9}, {13537ull, 2790790563858843297ull, 11}, {14221ull, 5313118889382907209ull, 12}, {14947ull, 5055052099144599145ull, 12}, {15727ull, 4804340543391258563ull, 12}, {16519ull, 4573997440881065647ull, 12}, {17351ull, 17418676439609088449ull, 14}, {18217ull, 2073828394519249147ull, 11}, {19139ull, 3947848044616454539ull, 12}, {20101ull, 15035642749298905213ull, 14}, {21107ull, 111867306648733719ull, 7}, {22189ull, 3405194633643441499ull, 12}, {23297ull, 6486488708925125417ull, 13}, {24473ull, 1543698437582526119ull, 11}, {25717ull, 2938051239488055505ull, 12}, {27011ull, 5594599513229004733ull, 13}, {28387ull, 2661706546162480129ull, 12}, {29819ull, 10135532878488792169ull, 14}, {31321ull, 9649482931696219587ull, 14}, {32887ull, 9189997716534110551ull, 14}, {34537ull, 17501893905299087569ull, 15}, {36263ull, 4167215273193851773ull, 13}, {38083ull, 3968062585716163297ull, 13}, {39989ull, 15115729570814838765ull, 15}, {41999ull, 14392316717238853005ull, 15}, {44101ull, 6853165572292176905ull, 14}, {46307ull, 6526690455085781711ull, 14}, {48623ull, 6215812576427972229ull, 14}, {51059ull, 11838518376923061309ull, 15}, {53611ull, 1409372399804411845ull, 12}, {56333ull, 2682543579284409615ull, 13}, {59149ull, 10219325936318696637ull, 15}, {62119ull, 9730725056863674357ull, 15}, {65239ull, 9265361360647995637ull, 15}, {68501ull, 4412073617956778641ull, 14}, {71933ull, 16806275556623930251ull, 16}, {75533ull, 8002633415954808989ull, 15}, {79309ull, 15243236197841722563ull, 16}, {83273ull, 7258810296342326893ull, 15}, {87481ull, 3454823960673258121ull, 14}, {91867ull, 13159522131065879747ull, 16}, {96461ull, 6266396883790491363ull, 15}, {101287ull, 11935646426635492953ull, 16}, {106357ull, 11366678447254333751ull, 16}, {111697ull, 5411630659796723165ull, 15}, {117281ull, 10307942630218272139ull, 16}, {123191ull, 76667394255581093ull, 9}, {129379ull, 9344065262636356555ull, 16}, {135851ull, 556181873713953695ull, 12}, {142657ull, 2118588326571127205ull, 14}, {149791ull, 16141501420173831201ull, 17}, {157279ull, 3843252499108683215ull, 15}, {165161ull, 7319680915074558611ull, 16}, {173431ull, 13941288692501677033ull, 17}, {182101ull, 13277530816575737363ull, 17}, {191227ull, 197560657558593513ull, 11}, {200789ull, 6020876739336463525ull, 16}, {210827ull, 11468415521869866523ull, 17}, {221399ull, 10920788437297631649ull, 17}, {232499ull, 10399406617788714573ull, 17}, {244157ull, 9902856109918037777ull, 17}, {256369ull, 9431138863237202429ull, 17}, {269189ull, 8981985293712812743ull, 17}, {282661ull, 8553891903125151151ull, 17}, {296797ull, 2036620686217564825ull, 15}, {311677ull, 7757555543813814781ull, 17}, {327263ull, 14776199198988326511ull, 18}, {343627ull, 14072535855618204329ull, 18}, {360817ull, 13402093799511987237ull, 18}, {378869ull, 6381761609498951747ull, 17}, {397811ull, 6077890353030103113ull, 17}, {417719ull, 1447056298150944983ull, 15}, {438611ull, 5512519383301509423ull, 17}, {460543ull, 5250001930827866995ull, 17}, {483611ull, 2499789747575280907ull, 16}, {507803ull, 9522793836307616731ull, 18}, {533213ull, 18137979675883808905ull, 19}, {559877ull, 17274162998153225437ull, 19}, {587891ull, 2056377491090404811ull, 16}, {617311ull, 7833496047306004103ull, 18}, {648181ull, 3730210603564835053ull, 17}, {680597ull, 14210180998325049035ull, 19}, {714673ull, 13532631786729082249ull, 19}, {750413ull, 12888111689052606229ull, 19}, {787981ull, 12273654513138049519ull, 19}, {827389ull, 11689068330515674487ull, 19}, {868771ull, 5566142606577011317ull, 18}, {912211ull, 10602159540848590291ull, 19}, {957821ull, 1262162574859633663ull, 16}, {1005761ull, 4808004365309965985ull, 18}, {1056049ull, 2289525996643392825ull, 17}, {1108867ull, 4360940742630555963ull, 18}, {1164323ull, 16612927094830272009ull, 20}, {1222561ull, 7910776277762036739ull, 19}, {1283701ull, 3767001255322319371ull, 18}, {1347893ull, 7175203489384567913ull, 19}, {1415303ull, 13666906036258007505ull, 20}, {1486081ull, 6507994218967225473ull, 19}, {1560407ull, 6198002544795706119ull, 19}, {1638431ull, 11805692832859038187ull, 20}, {1720361ull, 11243461758220551847ull, 20}, {1806379ull, 5354029556874295703ull, 19}, {1896761ull, 10197812541397712625ull, 20}, {1991603ull, 4856091578952749819ull, 19}, {2091191ull, 4624831761860601637ull, 19}, {2195749ull, 8809209574424976077ull, 20}, {2305549ull, 16779355471372819919ull, 21}, {2420827ull, 15980334913510190357ull, 21}, {2541899ull, 3715620866816223ull, 9}, {2668999ull, 14494432642225843319ull, 21}, {2802451ull, 6902105733100798835ull, 20}, {2942609ull, 3286677420247485615ull, 19}, {3089753ull, 3130155244421490455ull, 19}, {3244247ull, 11924377591369625553ull, 21}, {3406489ull, 354889101246071593ull, 16}, {3576847ull, 1351945799878640797ull, 18}, {3755729ull, 643776917671444971ull, 17}, {3943523ull, 9809915202134774817ull, 21}, {4140757ull, 4671322928110504141ull, 20}, {4347799ull, 2224437366335709953ull, 19}, {4565189ull, 16948094034077508551ull, 22}, {4793471ull, 4035241501165661959ull, 20}, {5033143ull, 240193020467455261ull, 16}, {5284819ull, 14640284266185136555ull, 22}, {5549087ull, 1742882488041191893ull, 19}, {5826577ull, 13279023422386122621ull, 22}, {6117919ull, 6323330895304127693ull, 21}, {6423821ull, 3011107114260199155ull, 20}, {6745021ull, 5735434512015327097ull, 21}, {7082311ull, 2731144271105020211ull, 20}, {7436459ull, 5202156863591681685ull, 21}, {7808329ull, 9908810509308235755ull, 22}, {8198783ull, 4718459584510058821ull, 21}, {8608727ull, 17975074004631873489ull, 23}, {9039167ull, 2139888898372390597ull, 20}, {9491137ull, 2037986925468894485ull, 20}, {9965699ull, 15527511407947654687ull, 23}, {10463987ull, 7394050896215397361ull, 22}, {10987189ull, 7041951536042227651ull, 22}, {11536549ull, 3353310095390582885ull, 21}, {12113417ull, 6387235943032116139ull, 22}, {12719107ull, 12166145383529876301ull, 23}, {13355101ull, 11586771594664281039ull, 23}, {14022871ull, 5517504400870283067ull, 22}, {14724029ull, 10509521878194652725ull, 23}, {15460229ull, 10009069394164377149ull, 23}, {16233247ull, 9532443195786556711ull, 23}, {17044913ull, 283703605788924631ull, 18}, {17897161ull, 2161550998377236121ull, 21}, {18792019ull, 4117240007863778085ull, 22}, {19731653ull, 1960587195997625419ull, 21}, {20718241ull, 3734450837565615111ull, 22}, {21754153ull, 3556619853475162521ull, 22}, {22841893ull, 211703262880117541ull, 18}, {23984003ull, 403244052167481525ull, 19}, {25183231ull, 6144664475764548813ull, 23}, {26442397ull, 11704120841289277547ull, 24}, {27764563ull, 5573381612765615449ull, 23}, {29152847ull, 5307972319501849489ull, 23}, {30610513ull, 5055207827149859735ull, 23}, {32141063ull, 9628959994924407719ull, 24}, {33748133ull, 18340867023449567935ull, 25}, {35435539ull, 8733746361847214141ull, 24}, {37207351ull, 16635691684761168229ull, 25}, {39067739ull, 1980438449620446865ull, 22}, {41021129ull, 15089053732350714615ull, 25}, {43072187ull, 3592631711751078123ull, 23}, {45225799ull, 3421553810705976347ull, 23}, {47487101ull, 13034487399908664407ull, 25}, {49861457ull, 1551724660900628459ull, 22}, {52354573ull, 5911327169478491759ull, 24}, {54972419ull, 11259646762910144767ull, 25}, {57721051ull, 5361735527326851147ull, 24}, {60607117ull, 5106413654708985229ull, 24}, {63637523ull, 1215811816800856111ull, 22}, {66819437ull, 2315830720194073685ull, 23}, {70160413ull, 17644423491141368779ull, 26}, {73668433ull, 16804212996974976717ull, 26}, {77351861ull, 16004011064263602849ull, 26}, {81219493ull, 15241907989814468245ull, 26}, {85280491ull, 14516098872899081631ull, 26}, {89544529ull, 6912426996435372813ull, 25}, {94021813ull, 6583259776565786255ull, 25}, {98722909ull, 12539541752009964323ull, 26}, {103659103ull, 1492801890352770411ull, 23}, {108842081ull, 11373726300633486371ull, 26}, {114284237ull, 2708028840594570087ull, 24}, {119998469ull, 10316298612821304203ull, 26}, {125998403ull, 9825045475261938637ull, 26}, {132298343ull, 9357184762966987991ull, 26}, {138913259ull, 8911604609934176801ull, 26}, {145858943ull, 8487241260793863527ull, 26}, {153151891ull, 2020771717545068175ull, 24}, {160809487ull, 15396355804373410817ull, 27}, {168849973ull, 14663194992460914103ull, 27}, {177292481ull, 6982473437694068227ull, 26}, {186157109ull, 13299949122924768615ull, 27}, {195464981ull, 12666617139828031651ull, 27}, {205238239ull, 12063444369013322853ull, 27}, {215500157ull, 11488994314610919517ull, 27}, {226275163ull, 1367737429588527437ull, 24}, {237588937ull, 10420855911194049199ull, 27}, {249468431ull, 9924622801555041447ull, 27}, {261941873ull, 2363005244460056745ull, 25}, {275038969ull, 9001924663885576701ull, 27}, {288790927ull, 1071657662643068661ull, 24}, {303230491ull, 16330020575475442869ull, 28}, {318392033ull, 1944049961962113975ull, 25}, {334311667ull, 7405903900358824599ull, 27}, {351027263ull, 14106483111374517653ull, 28}, {368578633ull, 3358686392668291965ull, 26}, {387007589ull, 6397497488274733935ull, 27}, {406357967ull, 12185709544957736979ull, 28}, {426675871ull, 11605437508186445115ull, 28}, {448009669ull, 11052797517058769327ull, 28}, {470410163ull, 10526473589690537999ull, 28}, {493930721ull, 1253151491345868599ull, 25}, {518627269ull, 2386955166611920429ull, 26}, {544558643ull, 18186324726615425695ull, 29}, {571786583ull, 17320309025654493539ull, 29}, {600375911ull, 8247766218490936589ull, 28}, {630394717ull, 15710030631939833023ull, 29}, {661914481ull, 14961933298877385037ull, 29}, {695010221ull, 3562364989407487505ull, 27}, {729760741ull, 3392728519731045041ull, 27}, {766248787ull, 12924679924202010123ull, 29}, {804561257ull, 6154609253253566869ull, 28}, {844789403ull, 11723064090427566833ull, 29}, {887028911ull, 11164822466855358449ull, 29}, {931380407ull, 166143182471598347ull, 23}, {977949439ull, 10126822430012194321ull, 29}, {1026846941ull, 2411148127061285709ull, 27}, {1078189297ull, 18370652244163470303ull, 30}, {1132098761ull, 17495859293291890105ull, 30}, {1188703709ull, 16662722996993765079ull, 30}, {1248138943ull, 991828711240989037ull, 26}, {1310545897ull, 7556790141385671897ull, 29}, {1376073217ull, 14393885720519829287ull, 30}, {1444876883ull, 13708462542109952491ull, 30}, {1517120861ull, 13055677459678727863ull, 30}, {1592977037ull, 12433977495286446115ull, 30}, {1672625909ull, 1480235398273243267ull, 27}, {1756257211ull, 11277983944782268227ull, 30}, {1844070071ull, 2685234273368086727ull, 28}, {1936273601ull, 10229463758807960115ull, 30}, {2033087339ull, 2435586539817373335ull, 28}, {2134741709ull, 9278424900333497161ull, 30}, {2241478829ull, 8836595006968091421ull, 30}, {2353552771ull, 16831609533148712559ull, 31}, {2471230409ull, 8015052160426083685ull, 30}, {2594791931ull, 7633383005369799109ull, 30}, {2724531541ull, 14539777081307853649ull, 31}, {2860758139ull, 13847406642694924025ull, 31}, {3003796087ull, 1648500768268535633ull, 28}, {3153985903ull, 12560005807081176671ull, 31}, {3311685211ull, 1495238780755457829ull, 28}, {3477269557ull, 2848073798117412443ull, 29}, {3651133121ull, 678112793075221469ull, 27}, {3833689799ull, 1291643407985999417ull, 28}, {4025374307ull, 9841092588146280131ull, 31}, {4226643191ull, 2343117189397746397ull, 29}, {4437975361ull, 17852321400993992043ull, 32}, {4659874133ull, 17002210843677381703ull, 32}, {4892867927ull, 16192581466804905563ull, 32}, {5137511359ull, 7710753025924778067ull, 31}, {5394386939ull, 7343574294000449121ull, 31}, {5664106297ull, 1748470066589049079ull, 29}, {5947311613ull, 3330419173811346145ull, 30}, {6244677209ull, 6343655553571170791ull, 31}, {6556911073ull, 377598544650989893ull, 27}, {6884756651ull, 1438470641201903855ull, 29}, {7228994671ull, 5479888014864490249ull, 31}, {7590444419ull, 10437881913204526107ull, 32}, {7969966657ull, 9940839896071391757ull, 32}, {8368465003ull, 9467466552810095751ull, 32}, {8786888267ull, 18033269595975923793ull, 33}, {9226232699ull, 8587271218820614487ull, 32}, {9687544343ull, 16356707068187576831ull, 33}, {10171921577ull, 15577816229611762685ull, 33}, {10680517669ull, 14836015438506801387ull, 33}, {11214543667ull, 14129538368538654083ull, 33}, {11775270853ull, 3364175801275912171ull, 31}, {12364034467ull, 12815907740426770131ull, 33}, {12982236217ull, 6102813197199147651ull, 32}, {13631348041ull, 1453050759836151439ull, 30}, {14312915467ull, 11070862913559934825ull, 33}, {15028561283ull, 10543678935372956631ull, 33}, {15779989387ull, 10041598960710928087ull, 33}, {16568988859ull, 9563427580099906155ull, 33}, {17397438323ull, 18216052511483149943ull, 34}, {18267310249ull, 8674310715076566125ull, 33}, {19180675771ull, 2065312073989917443ull, 31}, {20139709561ull, 15735711038790255491ull, 34}, {21146695051ull, 936649466065357335ull, 30}, {22204029811ull, 3568188440956526943ull, 32}, {23314231351ull, 6796549396930134083ull, 33}, {24479942941ull, 12945808363232710297ull, 34}, {25703940113ull, 12329341286349166121ull, 34}, {26989137127ull, 11742229792890160463ull, 34}, {28338593999ull, 11183075987052866009ull, 34}, {29755523717ull, 10650548552637237737ull, 34}, {31243299917ull, 10143379569346319199ull, 34}, {32805464957ull, 301886296300453383ull, 29}, {34445738207ull, 18400688535260071187ull, 35}, {36168025123ull, 8762232634469334069ull, 34}, {37976426413ull, 16689966907922255975ull, 35}, {39875247739ull, 15895206576840941963ull, 35}, {41869010171ull, 15138291961655333511ull, 35}, {43962460741ull, 7208710447854895029ull, 34}, {46160583811ull, 6865438516865931117ull, 34}, {48468613051ull, 6538512866534744747ull, 34}, {50892043747ull, 12454310211337850455ull, 35}, {53436645961ull, 2965311953601575993ull, 33}, {56108478299ull, 353013327558361135ull, 30}, {58913902231ull, 10758501408188866449ull, 35}, {61859597357ull, 10246191814929286119ull, 35}, {64952577353ull, 1219784737465925721ull, 32}, {68200206227ull, 2323399499718769013ull, 33}, {71610216569ull, 2212761427356502081ull, 33}, {75190727407ull, 16859134682479683775ull, 36}, {78950263811ull, 16056318738375259177ull, 36}, {82897777007ull, 15291732130780627285ull, 36}, {87042665867ull, 14563554408652673137ull, 36}, {91394799161ull, 6935025908832903385ull, 35}, {95964539119ull, 13209573159688603261ull, 36}, {100762766171ull, 3145136463594489011ull, 34}, {105800904527ull, 5990736118445611451ull, 35}, {111090949819ull, 11410925933153033577ull, 36}, {116645497313ull, 10867548507480633553ull, 36}, {122477772247ull, 2587511547956163001ull, 34}, {128601660959ull, 9857186841718740025ull, 36}, {135031744009ull, 9387796991970563815ull, 36}, {141783331211ull, 17881518079748447215ull, 37}, {148872497797ull, 17030017215896735325ull, 37}, {156316122691ull, 8109532007354575905ull, 36}, {164131928839ull, 3861681907947633321ull, 35}, {172338525313ull, 14711169170397987639ull, 37}, {180955451639ull, 7005318650234144005ull, 36}, {190003224311ull, 3335866022340022861ull, 35}, {199503385547ull, 794253814761447975ull, 33}, {209478554867ull, 12102915270091234561ull, 37}, {219952482619ull, 1440823246382769897ull, 34}, {230950106813ull, 5488850460912081057ull, 36}, {242497612171ull, 10454953258132132847ull, 37}, {254622492793ull, 9957098340552254979ull, 37}, {267353617439ull, 9482950800300724571ull, 37}, {280721298331ull, 18062763427854137777ull, 38}, {294757363253ull, 2150328979466685855ull, 35}, {309495231443ull, 511983090303967127ull, 33}, {324969993053ull, 7801647089437490025ull, 37}, {341218492723ull, 7430140084800760217ull, 37}, {358279417381ull, 7076323889854882177ull, 37}, {376193388269ull, 13478712170473192985ull, 38}, {395003057699ull, 3209217183311537233ull, 36}, {414753210583ull, 12225589269786240019ull, 38}, {435490871201ull, 5821709174900925211ull, 37}, {457265414773ull, 11088969856664348349ull, 38}, {480128685587ull, 5280461835678132219ull, 37}, {504135119923ull, 5029011271509298283ull, 37}, {529341875947ull, 2394767272021290201ull, 36}, {555808969759ull, 18245845881586049375ull, 39}, {583599418277ull, 17376996076806244003ull, 39}, {612779389213ull, 16549520072550591999ull, 39}, {643418358719ull, 7880723843516254105ull, 38}, {675589276709ull, 1876362819734705443ull, 36}, {709368740617ull, 14296097672707064803ull, 39}, {744837177653ull, 13615331116769731263ull, 39}, {782079036559ull, 3241745503896006575ull, 37}, {821182988387ull, 6174753340753922271ull, 38}, {862242137849ull, 2940358733546901847ull, 37}, {905354244917ull, 5600683300908115055ull, 38}, {950621957303ull, 5333984095316578539ull, 38}, {998153055223ull, 10159969704806606005ull, 39}, {1048060707989ull, 2419040405895140425ull, 37}, {1100463743389ull, 9215392022453072055ull, 39}, {1155486930613ull, 17553127660986700359ull, 40}, {1213261277161ull, 16717264438795890829ull, 40}, {1273924341023ull, 7960602113687645885ull, 39}, {1337620558103ull, 3790762911198071633ull, 38}, {1404501586093ull, 14441001565596421675ull, 40}, {1474726665421ull, 13753334824159781815ull, 40}, {1548462998851ull, 13098414116902856733ull, 40}, {1625886148903ull, 6237340055248147143ull, 39}, {1707180456391ull, 11880647723983982373ull, 40}, {1792539479293ull, 2828725648437504227ull, 38}, {1882166453477ull, 5388048853538744859ull, 39}, {1976274776167ull, 10262950197132788655ull, 40}, {2075088514987ull, 9774238282928733535ull, 40}, {2178842940751ull, 9308798364631441885ull, 40}, {2287785087839ull, 8865522251834443073ull, 40}, {2402174342237ull, 16886709051070694853ull, 41}, {2522283059347ull, 4020645012162638243ull, 39}, {2648397212317ull, 59831026966646059ull, 33}, {2780817072931ull, 14587374193782458005ull, 41}, {2919857926577ull, 13892737327414481677ull, 41}, {3065850822911ull, 13231178407039185457ull, 41}, {3219143364077ull, 12601122292338221701ull, 41}, {3380100532351ull, 1500133606199607175ull, 38}, {3549105559033ull, 5714794690180439967ull, 40}, {3726560837047ull, 2721330804802297305ull, 39}, {3912888879007ull, 5183487247099864809ull, 40}, {4108533323047ull, 9873309041879540653ull, 41}, {4313959989413ull, 9403151467991011841ull, 41}, {4529657988913ull, 17910764700819207529ull, 42}, {4756140888377ull, 17057871143571528337ull, 42}, {4993947932801ull, 8122795782644732113ull, 41}, {5243645329459ull, 15471991966889383297ull, 42}, {5505827595941ull, 1841903805579041879ull, 39}, {5781118975739ull, 14033552804409441543ull, 42}, {6070174924579ull, 6682644192517521899ull, 41}, {6373683670811ull, 12728846080979664861ull, 42}, {6692367854377ull, 12122710553267865813ull, 42}, {7026986247119ull, 11545438622121836423ull, 42}, {7378335559501ull, 5497827915276701915ull, 41}, {7747252337609ull, 5236026585887956299ull, 41}, {8134614954497ull, 9973383973110660139ull, 42}, {8541345702271ull, 9498460926717399687ull, 42}, {8968412987389ull, 9046153263535892081ull, 42}, {9416833636757ull, 17230768121023400007ull, 43}, {9887675318611ull, 16410255353328815421ull, 43}, {10382059084633ull, 3907203655520063397ull, 41}, {10901162038883ull, 14884585354337090951ull, 43}, {11446220140841ull, 14175795575541981435ull, 43}, {12018531147923ull, 13500757690947486301ull, 43}, {12619457705359ull, 6428932233764215863ull, 42}, {13250430590651ull, 12245585207147708807ull, 43}, {13912952120191ull, 5831231051019596017ull, 42}, {14608599726313ull, 11107106763761352371ull, 43}, {15339029712647ull, 5289098458927649999ull, 42}, {16105981198301ull, 10074473255086743393ull, 43}, {16911280258291ull, 9594736433373422667ull, 43}, {17756844271213ull, 4568922111128284349ull, 42}, {18644686484807ull, 17405417566171854693ull, 44}, {19576920809087ull, 16576588158225335937ull, 44}, {20555766849589ull, 15787226817320866675ull, 44}, {21583555192079ull, 15035454111726809437ull, 44}, {22662732951713ull, 14319480106387498043ull, 44}, {23795869599331ull, 3409400025325721667ull, 42}, {24985663079317ull, 811761910791206579ull, 40}, {26234946233311ull, 6184852653640651897ull, 43}, {27546693545051ull, 5890335860594224949ull, 43}, {28924028222329ull, 5609843676751468661ull, 43}, {30370229633461ull, 10685416527140183503ull, 44}, {31888741115167ull, 10176587168694421405ull, 44}, {33483178170971ull, 4845993889847879495ull, 43}, {35157337079519ull, 9230464552091343439ull, 44}, {36915203933497ull, 8790918621038886521ull, 44}, {38760964130257ull, 16744606897180142191ull, 45}, {40699012336781ull, 15947244663976718855ull, 45}, {42733962953639ull, 7593926030461736757ull, 44}, {44870661101341ull, 14464621010396844739ull, 45}, {47114194156493ull, 13775829533686441975ull, 45}, {49469903864351ull, 13119837651121100035ull, 45}, {51943399057603ull, 12495083477249903497ull, 45}, {54540569010611ull, 5950039751057434971ull, 44}, {57267597461141ull, 11333409049633318315ull, 45}, {60130977334199ull, 10793722904412513581ull, 45}, {63137526200921ull, 2569934024859631801ull, 43}, {66294402511313ull, 4895112428278515971ull, 44}, {69609122636917ull, 9324023672906322075ull, 45}, {73089578768803ull, 17760045091240381233ull, 46}, {76744057707277ull, 8457164329158356045ull, 45}, {80581260592649ull, 8054442218245238749ull, 45}, {84610323622289ull, 7670897350709066695ull, 45}, {88840839803449ull, 14611233048962159455ull, 46}, {93282881793631ull, 1739432505828650429ull, 43}, {97947025883323ull, 13252819092026398845ull, 46}, {102844377177559ull, 12621732468587997881ull, 46}, {107986596036437ull, 3005174397282855247ull, 44}, {113385925838287ull, 2862070854554389677ull, 44}, {119055222130219ull, 10903127064967487137ull, 46}, {125007983236757ull, 10383930538062026525ull, 46}, {131258382398683ull, 9889457655290526595ull, 46}, {137821301518801ull, 4709265550132063961ull, 45}, {144712366594753ull, 4485014809649214363ull, 45}, {151947984924497ull, 17085770703424864501ull, 47}, {159545384170751ull, 16272162574687374111ull, 47}, {167522653379297ull, 3874324422544417459ull, 45}, {175898786048299ull, 3689832783374856379ull, 45}, {184693725350723ull, 14056505841427335531ull, 47}, {193928411618287ull, 836696776275316481ull, 43}, {203624832199223ull, 12749665162289181271ull, 47}, {213806073809197ull, 12142538249798490477ull, 47}, {224496377499701ull, 5782161071331477379ull, 46}, {235721196374689ull, 11013640135869342889ull, 47}, {247507256193427ull, 5244590540890088057ull, 46}, {259882619003297ull, 4994848134177218265ull, 46}, {272876749953557ull, 4756998223024263429ull, 46}, {286520587451237ull, 4530474498118312127ull, 46}, {300846616823833ull, 17258950469020182321ull, 48}, {315888947665051ull, 16437095684779754913ull, 48}, {331683395048363ull, 15654376842644579785ull, 48}, {348267564800807ull, 14908930326327064615ull, 48}, {365680943040869ull, 7099490631583896161ull, 47}, {383964990193007ull, 3380709824562927589ull, 46}, {403163239702661ull, 6439447284881708537ull, 47}, {423321401687831ull, 12265613875964088503ull, 48}, {444487471772237ull, 11681537024727323577ull, 48}, {466711845360847ull, 11125273356883209411ull, 48}, {490047437628913ull, 1324437304390794345ull, 45}, {514549809510377ull, 10090950890596168477ull, 48}, {540277299986003ull, 4805214709806746285ull, 47}, {567291164985341ull, 18305579846881621631ull, 49}, {595655723234653ull, 8716942784228685827ull, 48}, {625438509396409ull, 4150925135346838281ull, 47}, {656710434866231ull, 3953262033663646175ull, 47}, {689545956609611ull, 15060045842526680921ull, 49}, {724023254440627ull, 14342900802395755517ull, 49}, {760224417162697ull, 6829952763045250629ull, 48}, {798235638020831ull, 13009433834371919813ull, 49}, {838147419921883ull, 6194968492557979815ull, 48}, {880054790918011ull, 5899969992912134795ull, 48}, {924057530463983ull, 5619019040868265331ull, 48}, {970260406987181ull, 10702893411177660935ull, 49}, {1018773427336681ull, 5096615910083895315ull, 48}, {1069712098703531ull, 4853919914365542211ull, 48}, {1123197703638737ull, 4622780870824204707ull, 48}, {1179357588820721ull, 8805296896807656935ull, 49}, {1238325468261769ull, 16771994089157279929ull, 50}, {1300241741674879ull, 15973327703959049479ull, 50}, {1365253828758623ull, 15212693051389570375ull, 50}, {1433516520196571ull, 905517443535082831ull, 46}, {1505192346206447ull, 13798361044343684347ull, 50}, {1580451963516779ull, 1642662029088523821ull, 47}, {1659474561692683ull, 6257760110813178781ull, 49}, {1742448289777331ull, 11919543068215483887ull, 50}, {1829570704266313ull, 1418993222406515683ull, 47}, {1921049239479793ull, 10811376932620146933ull, 50}, {2017101701453837ull, 5148274729818978869ull, 49}, {2117956786526611ull, 1225779697575899805ull, 47}, {2223854625852991ull, 9339273886292362273ull, 50}, {2335047357145673ull, 17789093116747109497ull, 51}, {2451799725002977ull, 16941993444520916045ull, 51}, {2574389711253163ull, 8067615925962224553ull, 50}, {2703109196815823ull, 7683443739011637173ull, 50}, {2838264656656643ull, 14635130931450588711ull, 51}, {2980177889489539ull, 13938219934714547767ull, 51}, {3129186783964027ull, 13274495175918570045ull, 51}, {3285646123162259ull, 12642376358017567823ull, 51}, {3449928429320413ull, 12040358436207064185ull, 51}, {3622424850786461ull, 11467008034482831693ull, 51}, {3803546093325871ull, 10920960032840542433ull, 51}, {3993723397992173ull, 10400914316990970787ull, 51}, {4193409567891821ull, 4952816341424225327ull, 50}, {4403080046286421ull, 9433935888427076685ull, 51}, {4623234048600743ull, 561543802882563973ull, 47}, {4854395751030779ull, 17113715897373382279ull, 52}, {5097115538582321ull, 4074694261279374295ull, 50}, {5351971315511461ull, 7761322402436868687ull, 51}, {5619569881287097ull, 7391735621368363567ull, 51}, {5900548375351481ull, 7039748210826978143ull, 51}, {6195575794119307ull, 13409044211098460693ull, 52}, {6505354583825287ull, 99769674189720465ull, 45}, {6830622313016639ull, 12162398377413386333ull, 52}, {7172153428667531ull, 11583236549917413811ull, 52}, {7530761100100921ull, 11031653857064183927ull, 52}, {7907299155105991ull, 5253168503363881197ull, 51}, {8302664112861337ull, 1250754405562821859ull, 49}, {8717797318504493ull, 4764778687858320261ull, 51}, {9153687184429741ull, 9075768929253920203ull, 52}, {9611371543651247ull, 17287178912864575827ull, 53}, {10091940120833861ull, 8231989958506898739ull, 52}, {10596537126875629ull, 15679980873346362883ull, 53}, {11126363983219531ull, 7466657558736282379ull, 52}, {11682682182380519ull, 14222204873783381069ull, 53}, {12266816291499617ull, 3386239255662689889ull, 51}, {12880157106074683ull, 1612494883648889287ull, 50}, {13524164961378517ull, 12285675303991446719ull, 53}, {14200373209447571ull, 11700643146658415093ull, 53}, {14910391869919981ull, 5571734831742090673ull, 52}, {15655911463415981ull, 2653207062734328731ull, 51}, {16438707036586829ull, 10107455477083126973ull, 53}, {17260642388416249ull, 1203268509176557259ull, 50}, {18123674507837099ull, 9167760069916607741ull, 53}, {19029858233228981ull, 17462400133174466113ull, 54}, {19981351144890479ull, 16630857269689926985ull, 54}, {20980418702135003ull, 15838911685418978043ull, 54}, {22029439637241899ull, 15084677795637022075ull, 54}, {23130911619104053ull, 14366359805368555777ull, 54}, {24287457200059267ull, 13682247433684332441ull, 54}, {25501830060062243ull, 13030711841604119671ull, 54}, {26776921563065419ull, 193909402404822747ull, 48}, {28115767641218743ull, 11819239765627268945ull, 54}, {29521556023279703ull, 2814104706101728523ull, 52}, {30997633824443711ull, 670024930024220583ull, 50}, {32547515515665947ull, 10209903695607154963ull, 54}, {34174891291449269ull, 4861858902670070285ull, 53}, {35883635856021739ull, 9260683624133465519ull, 54}, {37677817648822853ull, 4409849344825456605ull, 53}, {39561708531264013ull, 4199856518881385401ull, 53}, {41539793957827267ull, 15999453405262400027ull, 55}, {43616783655718643ull, 15237574671678471797ull, 55}, {45797622838504627ull, 14511975877789004329ull, 55}, {48087503980429867ull, 13820929407418096875ull, 55}, {50491879179451373ull, 13162789911826755631ull, 55}, {53016473138423957ull, 6267995196107977057ull, 54}, {55667296795345217ull, 11939038468777085827ull, 55}, {58450661635112503ull, 5685256413703371757ull, 54}, {61373194716868207ull, 10829059835625456101ull, 55}, {64441854452711651ull, 10313390319643286139ull, 55}, {67663947175347401ull, 2455569123724585861ull, 53}, {71047144534114849ull, 4677274521380158413ull, 54}, {74599501760820593ull, 1113636790804799599ull, 52}, {78329476848861697ull, 16969703478930263497ull, 56}, {82245950691304817ull, 2020202795110744791ull, 53}, {86358248225870107ull, 7696010648040928157ull, 55}, {90676160637163627ull, 7329533950515168489ull, 55}, {95209968669021809ull, 3490254262150080209ull, 54}, {99970467102473027ull, 6648103356476334773ull, 55}, {104968990457596879ull, 12663054012335851553ull, 56}, {110217439980476921ull, 12060051440319836951ull, 56}, {115728311979501007ull, 2871440819123764749ull, 54}, {121514727578476087ull, 2734705542022632427ull, 54}, {127590463957399943ull, 5208962937185964419ull, 55}, {133969987155270011ull, 1240229270758562301ull, 53}, {140668486513033511ull, 9449365872446188997ull, 56}, {147701910838685293ull, 17998792137992727975ull, 57}, {155087006380619567ull, 17141706798088311323ull, 57}, {162841356699650569ull, 8162717522899194683ull, 56}, {170983424534633129ull, 7774016688475422073ull, 56}, {179532595761364817ull, 14807650835191277537ull, 57}, {188509225549433093ull, 14102524604944071215ull, 57}, {197934686826904793ull, 13430975814232445699ull, 57}, {207831421168250129ull, 12791405537364228069ull, 57}, {218222992226662673ull, 6091145493982964699ull, 56}, {229134141837995873ull, 11602181893300881781ull, 57}, {240590848929895999ull, 5524848520619459883ull, 56}, {252620391376390847ull, 10523520991656112061ull, 57}, {265251410945210549ull, 10022400944434386407ull, 57}, {278513981492471381ull, 9545143756604167093ull, 57}, {292439680567094981ull, 18181226203055554443ull, 58}, {307061664595449749ull, 270553961354993353ull, 52}, {322414747825222259ull, 16490908120685307981ull, 58}, {338535485216483417ull, 7852813390802526565ull, 57}, {355462259477307673ull, 7478869896002404461ull, 57}, {373235372451173171ull, 14245466468576004133ull, 58}, {391897141073731841ull, 13567110922453336873ull, 58}, {411491998127418553ull, 12921058021384126589ull, 58}, {432066598033789489ull, 6152884772087679209ull, 57}, {453669927935478967ull, 11719780518262246021ull, 58}, {476353424332252979ull, 2790423932919582013ull, 56}, {500171095548865693ull, 5315093205561107905ull, 57}, {525179650326309179ull, 10123987058211630223ull, 58}, {551438632842624641ull, 9641892436392028731ull, 58}, {579010564484755961ull, 18365509402651480507ull, 59}, {607961092708993897ull, 17490961335858548895ull, 59}, {638359147344443641ull, 16658058415103378617ull, 59}, {670277104711665961ull, 495775548068552833ull, 54}, {703790959947249319ull, 15109350036374942195ull, 59}, {738980507944611817ull, 3597464294374986081ull, 57}, {775929533341842413ull, 13704625883333280217ull, 59}, {814726010008934533ull, 13052024650793600217ull, 59}, {855462310509381313ull, 6215249833711237811ull, 58}, {898235426034850433ull, 184977673622358257ull, 53}, {943147197336593023ull, 11274829630315169133ull, 59}, {990304557203422691ull, 10737932981252541849ull, 59}, {1039819785063593969ull, 10226602839288133683ull, 59}, {1091810774316773677ull, 9739621751702984375ull, 59}, {1146401313032612359ull, 9275830239717127991ull, 59}, {1203721378684243091ull, 8834124037825835345ull, 59}, {1263907447618455529ull, 8413451464596031775ull, 59}, {1327102819999378337ull, 16025621837325774429ull, 60}, {1393457960999347253ull, 15262496987929308989ull, 60}, {1463130859049314661ull, 908481963567220745ull, 56}, {1536287402001780431ull, 6921767341464538843ull, 59}, {1613101772101869463ull, 1648039843205842571ull, 57}, {1693756860706962959ull, 6278247021736543043ull, 59}, {1778444703742311217ull, 11958565755688652675ull, 60}, {1867366938929426969ull, 5694555121756500691ull, 59}, {1960735285875898321ull, 10846771660488572725ull, 60}, {2058772050169693399ull, 5165129362137415177ull, 59}, {2161710652678178227ull, 2459585410541626095ull, 58}, {2269796185312087163ull, 9369849183015718355ull, 60}, {2383285994577691523ull, 17847331777172796853ull, 61}, {2502450294306576181ull, 8498729417701331557ull, 60}, {2627572809021905011ull, 4047014008429205471ull, 59}, {2758951449473000293ull, 7708598111293724619ull, 60}, {2896899021946650319ull, 14683044021511856359ull, 61}, {3041743973043982909ull, 6991925724529455239ull, 60}, {3193831171696182079ull, 13317953761008486067ull, 61}, {3353522730280991201ull, 12683765486674748567ull, 61}, {3521198866795040881ull, 12079776653975950605ull, 61}, {3697258810134792971ull, 11504549194262809957ull, 61}, {3882121750641532621ull, 1369589189793191661ull, 58}, {4076227838173609267ull, 5217482627783587261ull, 60}, {4280039230082289733ull, 38820555266246929ull, 53}, {4494041191586404219ull, 2366205273371241387ull, 59}, {4718743251165724471ull, 9014115327128538539ull, 61}, {4954680413724010873ull, 8584871740122417347ull, 61}, {5202414434410211531ull, 16352136647852223159ull, 62}, {5462535156130722121ull, 7786731737072487199ull, 61}, {5735661913937258341ull, 14831869975376165799ull, 62}, {6022445009634121283ull, 1765698806592400683ull, 59}, {6323567260115827453ull, 6726471644161526299ull, 61}, {6639745623121618859ull, 12812326941260050029ull, 62}, {6971732904277699861ull, 12202216134533380877ull, 62}, {7320319549491584971ull, 11621158223365124459ull, 62}, {7686335526966164273ull, 11067769736538213693ull, 62}, {8070652303314472717ull, 5270366541208673037ull, 61}, {8474184918480196373ull, 627424588239127741ull, 58}, {8897894164404206201ull, 2390188907577629487ull, 60}, {9342788872624416551ull, 9105481552676683721ull, 62}, {9809928316255637389ull, 17343774386050826117ull, 63}, {10300424732068419343ull, 16517880367667453309ull, 63}, {10815445968671840317ull, 7865657317936882523ull, 62}, {11356218267105432353ull, 7491102207558935723ull, 62}, {11924029180460704009ull, 7134383054818033999ull, 62}, {12520230639483739223ull, 6794650528398127611ull, 62}, {13146242171457926281ull, 3235547870665775029ull, 61}, {13803554280030822631ull, 12325896650155333411ull, 63}, {14493731994032363789ull, 11738949190624127037ull, 63}, {15218418593733982013ull, 1397493951264777025ull, 60}, {15979339523420681189ull, 1330946620252168589ull, 60}, {16778306499591715409ull, 10140545678111760581ull, 63}, {17617221824571301183ull, 9657662550582629123ull, 63}}; /// The value itself const uint64_t value = 0; /// The magic multiplication number const uint64_t magic = 0; /// The shift after multiplication const uint64_t shift = 0; public: /// Default construction, represents the value 0 constexpr Prime() noexcept = default; /// Explicit construction constexpr Prime(uint64_t v, uint64_t m, uint64_t s) noexcept : value(v), magic(m), shift(s) {} /// Explicit construction constexpr Prime(Number n) noexcept : value(n.value), magic(n.magic), shift(n.shift) {} /// Get the value of the prime number constexpr uint64_t get() const noexcept { return value; } /// Divide the argument by the prime number constexpr uint64_t div(uint64_t x) const noexcept { return static_cast((static_cast(x) * magic) >> 64) >> shift; } /// Return the remainder after division constexpr uint64_t mod(uint64_t x) const noexcept { return x - div(x) * value; } /// Pick a suitable prime number larger than the argument static constexpr Prime pick(uint64_t desiredSize) noexcept { // Sanity check, should never happen for practical usage as we are close to 2^64 if (desiredSize >= primes[primeCount - 1].value) return primes[primeCount - 1]; // Pick a number unsigned lower = 0, upper = primeCount - 1; while (lower != upper) { unsigned middle = lower + ((upper - lower) / 2); if (primes[middle].value < desiredSize) { lower = middle + 1; } else if (primes[middle].value > desiredSize) { upper = middle; } else { return primes[middle]; } } return primes[lower]; } }; //--------------------------------------------------------------------------- } //--------------------------------------------------------------------------- #endif