1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

/*
* This file is part of the uutils coreutils package.
*
* (c) kwantam <kwantam@gmail.com>
*
* For the full copyright and license information, please view the LICENSE file
* that was distributed with this source code.
*/

// *** NOTE: this file was automatically generated.
// Please do not edit by hand. Instead, modify and
// re-run src/factor/gen_tables.rs.

#[allow(clippy::unreadable_literal)]
pub const PRIME_INVERSIONS_U64: &[(u64, u64, u64)] = &[
    (3, 12297829382473034411, 6148914691236517205), (5, 14757395258967641293, 3689348814741910323),
    (7, 7905747460161236407, 2635249153387078802), (11, 3353953467947191203, 1676976733973595601),
    (13, 5675921253449092805, 1418980313362273201), (17, 17361641481138401521, 1085102592571150095),
    (19, 9708812670373448219, 970881267037344821), (23, 15238614669586151335, 802032351030850070),
    (29, 3816567739388183093, 636094623231363848), (31, 17256631552825064415, 595056260442243600),
    (37, 1495681951922396077, 498560650640798692), (41, 10348173504763894809, 449920587163647600),
    (43, 9437869060967677571, 428994048225803525), (47, 5887258746928580303, 392483916461905353),
    (53, 2436362424829563421, 348051774975651917), (59, 14694863923124558067, 312656679215416129),
    (61, 5745707170499696405, 302405640552615600), (67, 17345445920055250027, 275324538413575397),
    (71, 1818693077689674103, 259813296812810586), (73, 9097024474706080249, 252695124297391118),
    (79, 11208148297950107311, 233503089540627235), (83, 11779246215742243803, 222249928598910260),
    (89, 17617676924329347049, 207266787345051141), (97, 11790702397628785569, 190172619316593315),
    (101, 4200743699953660269, 182641030432767837), (103, 15760325033848937303, 179094602657374287),
    (107, 8619973866219416643, 172399477324388332), (109, 12015769075535579493, 169236184162472950),
    (113, 10447713457676206225, 163245522776190722), (127, 9150747060186627967, 145249953336295682),
    (131, 281629680514649643, 140814840257324821), (137, 16292379802327414201, 134647766961383588),
    (139, 4246732448623781667, 132710389019493177), (149, 16094474695182830269, 123803651501406386),
    (151, 8062815290495565607, 122163868037811600), (157, 6579730370240349621, 117495185182863386),
    (163, 2263404180823257867, 113170209041162893), (167, 10162278172342986519, 110459545351554201),
    (173, 9809829218388894501, 106628578460748853), (179, 17107036403551874683, 103054436165975148),
    (181, 3770881385233444253, 101915713114417412), (191, 2124755861893246783, 96579811904238490),
    (193, 8124213711219232577, 95578984837873324), (197, 14513935692512591373, 93638294790403815),
    (199, 2780916192016515319, 92697206400550510), (211, 13900627050804827995, 87425327363552377),
    (223, 7527595115280579359, 82720825442643729), (227, 1950316554048586955, 81263189752024456),
    (229, 2094390156840385773, 80553467570784068), (233, 7204522363551799129, 79170575423646144),
    (239, 7255204782128442895, 77183029597111094), (241, 17298606475760824337, 76542506529915151),
    (251, 2939720171109091891, 73493004277727297), (257, 18374966859414961921, 71777214294589695),
    (263, 15430736487513693367, 70139711306880424), (269, 10354863773718001093, 68575256779589411),
    (271, 15383631589145234927, 68069166323651481), (277, 17181443938689762877, 66594743948409933),
    (281, 14245350405676059433, 65646776063023315), (283, 5149444458738708755, 65182841249857072),
    (293, 2707201348701401773, 62958170900032599), (307, 17305088903023944187, 60087114246610917),
    (311, 9134400602415662215, 59314289626075728), (313, 6365010734698503433, 58935284580541698),
    (317, 17050145153302519317, 58191621683626345), (331, 3455281367280943203, 55730344633563600),
    (337, 9196002980365592497, 54738112978366622), (347, 9941040754419844819, 53160645745560667),
    (349, 15751088062938241781, 52856000211202153), (353, 8779186981255537313, 52257065364616293),
    (359, 5600822016808749655, 51383688227603207), (367, 9751139919072624015, 50263607830271257),
    (373, 3511310534137743069, 49455077945602015), (379, 17181268226964305331, 48672147951740241),
    (383, 14834457375202459263, 48163822646761231), (389, 12661389891209383757, 47420935922132523),
    (397, 185861401246443845, 46465350311610961), (401, 3220129888178724721, 46001855545410353),
    (409, 2074694932495450793, 45102063749901104), (419, 1849076971589024267, 44025642180691053),
    (421, 14897608040525528621, 43816494236839790), (431, 8046375605237577039, 42799870240625409),
    (433, 7540585914657253201, 42602180308798040), (439, 15379290047785184263, 42019918163347497),
    (443, 15615189678648040307, 41640505809728107), (449, 205420312624827969, 41084062524965593),
    (457, 686202733595322489, 40364866682077793), (461, 3041111821262312197, 40014629227135686),
    (463, 8127723090792113455, 39841779856824085), (467, 15247201739725667931, 39500522641776341),
    (479, 8010277176057592351, 38510947961815347), (487, 2386334448960373207, 37878324586672590),
    (491, 1051952818867347139, 37569743530976683), (499, 12494988971771199291, 36967422993405915),
    (503, 17969989256695189447, 36673447462643243), (509, 5436172123882971989, 36241147492553146),
    (521, 1805727346946616377, 35406418567580713), (523, 7195288319381928355, 35271021173440825),
    (541, 13911777416032342069, 34097493666745936), (547, 13219604528142859659, 33723480939139948),
    (557, 5133295029488295333, 33118032448311582), (563, 18151858289227516155, 32765087164670606),
    (569, 6386658317259721737, 32419585366800617), (571, 1873749835858413299, 32306031652731263),
    (577, 8184343991108570561, 31970093715267853), (587, 8107768264083584867, 31425458387920871),
    (593, 13407330009728190129, 31107494222107169), (599, 16999336775772408167, 30795899956109435),
    (601, 10926856722530117097, 30693417759916059), (607, 7810235958720518559, 30390023185682951),
    (613, 10111102787547160429, 30092567820080834), (617, 5112468778937331161, 29897478239399597),
    (619, 10400506755613301315, 29800878955912038), (631, 14909412801254946631, 29234142747558718),
    (641, 18417966001831689601, 28778071877862015), (643, 12450835035754191915, 28688559990217032),
    (647, 16650538700226241335, 28511196404496988), (653, 18023005695293558853, 28249225227732850),
    (659, 13744083976011213723, 27992024391061535), (661, 3544230707051608253, 27907328401981167),
    (673, 7016889276180750689, 27409723735081057), (677, 7711120491668837677, 27247775588935822),
    (683, 18338710433453565955, 27008410063996415), (691, 16604739238563445883, 26695722248494285),
    (701, 4578792394900801685, 26314898821268975), (709, 17796294705807240205, 26017974716092456),
    (719, 7799457855921701935, 25656111368163493), (727, 3501582781529460967, 25373788271952615),
    (733, 8027982755134170485, 25166090141486427), (739, 12755461734324196043, 24961764646426998),
    (743, 8416482154761154775, 24827380987496031), (751, 73688724661955599, 24562908220651866),
    (757, 11233750354002778461, 24368222026036395), (761, 8193166224591101769, 24240136759145271),
    (769, 8635666926574042369, 23987963684927895), (773, 11955781087876436429, 23863834506739394),
    (787, 1757948926973591323, 23439319026314550), (797, 3332912354597459765, 23145224684704581),
    (809, 12062209660064712985, 22801908620160137), (811, 2229076349227541379, 22745677032934095),
    (821, 4044353146489304861, 22468628591607249), (823, 5536264624794968711, 22414026821032261),
    (827, 9502192231439261171, 22305615566758829), (829, 9813044796750195733, 22251802260204525),
    (839, 17941052639030982263, 21986584116459537), (853, 13018686907823153661, 21625725760503577),
    (857, 12247604875076703465, 21524788884141833), (859, 858986918449804499, 21474672961245112),
    (863, 13637338028999645343, 21375137976488472), (877, 4964004106494246501, 21033915705484095),
    (881, 14447506709261737361, 20938415520669184), (883, 17047047751015848379, 20890989890950794),
    (887, 15763959422628906567, 20796780240935232), (907, 11979197639928253475, 20338196332645591),
    (911, 16462352285319281519, 20248895799900715), (919, 16098246732442938407, 20072626848432591),
    (929, 13264181960428396641, 19856559821000593), (937, 11792529028977610905, 19687026759561954),
    (941, 1725094026021722149, 19603341204792297), (947, 18271431828024877947, 19479138409408185),
    (953, 18137040080866579081, 19356499552685783), (967, 9614435380713147895, 19076260676018150),
    (971, 10828675717831559651, 18997676697950104), (977, 12064963626510136625, 18881007240234955),
    (983, 9326583728009813991, 18765762028188760), (991, 13160290676198438943, 18614272526447579),
    (997, 11785933776281829869, 18502250826188115), (1009, 6965519813759503633, 18282204235589248),
    (1013, 7775675932353384541, 18210013893099261), (1019, 10372899268140896051, 18102791043875909),
    (1021, 7497942008412795221, 18067330140753723), (1031, 13544311604071901623, 17892089305246897),
    (1033, 15464550210873641529, 17857448280454551), (1039, 1881958490676816623, 17754325383743553),
    (1049, 8370495880920635433, 17585075380085368), (1051, 15691141010367591955, 17551611868420125),
    (1061, 10466484384894580653, 17386186685871396), (1063, 5917535022704569239, 17353475139896097),
    (1069, 13511506650808773541, 17256074905247475), (1087, 4836542834413267903, 16970325734783396),
    (1091, 12613447368457676907, 16908106392034419), (1093, 12235946434985750157, 16877167496532069),
    (1097, 14007418243755748857, 16815628143764404), (1103, 13546566364192871087, 16724156005176384),
    (1109, 14687533829653321981, 16633673646266502), (1117, 17043007953507839989, 16514542590608372),
    (1123, 10923494932339137867, 16426308168931034), (1129, 8610659102608444377, 16339011579902171),
    (1151, 2852754513571068799, 16026710750399262), (1153, 16894849732729650049, 15998910731751562),
    (1163, 14877941479913636643, 15861344861315177), (1171, 10554499171123313051, 15752983837497482),
    (1181, 9918444103984390581, 15619597014148646), (1187, 6884505159775342347, 15540643701524474),
    (1193, 17503532515875282841, 15462484554660143), (1201, 10275496907003905105, 15359487155461741),
    (1213, 12439766407497455253, 15207538395473661), (1217, 6745111842892974913, 15157554703130280),
    (1223, 5399782811437464823, 15083192210719175), (1229, 11572367518982965253, 15009555796346258),
    (1231, 1168843247562424879, 14985169840543908), (1237, 12988774525627339901, 14912485104049758),
    (1249, 2171073962238033697, 14769210627469616), (1259, 2754557494723904451, 14651901567680342),
    (1277, 8710561218830743637, 14445375155606540), (1279, 10802667170608642815, 14422786609624356),
    (1283, 17756608675784330667, 14377820790108769), (1289, 715544766241642809, 14310895324832856),
    (1291, 10173572254439349923, 14288725076459761), (1297, 9401154844041645041, 14222624574949538),
    (1301, 4069343235322552893, 14178896290322483), (1303, 17455744775812645543, 14157132827098658),
    (1307, 11545093077501463827, 14113805718216948), (1319, 7286393982109686423, 13985401117293064),
    (1321, 10375420777264342809, 13964227156479600), (1327, 17848997280062595535, 13901088224347815),
    (1361, 8864195903163884465, 13553816365694012), (1367, 11915490136858474087, 13494326315808011),
    (1373, 7241656996161287925, 13435356208091443), (1381, 10365440551193781357, 13357526483497140),
    (1399, 11511084757933122631, 13185664098434275), (1409, 11062809611273648769, 13092082380205501),
    (1423, 11991031811792927087, 12963277634370731), (1427, 10910337770294927515, 12926940486131430),
    (1429, 4001742941112638909, 12908848197137544), (1433, 6539390083352723113, 12872815124710084),
    (1439, 3589359513994909279, 12819141121410390), (1447, 15973580044476895767, 12748268191920906),
    (1451, 6496406768894266627, 12713124792356686), (1453, 16301183338364118565, 12695625652931556),
    (1459, 12921571242858918267, 12643416088903051), (1471, 15612641993044453951, 12540274693208396),
    (1481, 7535638193514030201, 12455600319857901), (1483, 10846635760131307491, 12438802477214802),
    (1487, 7517637463798243631, 12405342349502052), (1489, 9155234298503263025, 12388679700275051),
    (1493, 17211195240909179773, 12355488328003718), (1499, 11419998999601376851, 12306033404742862),
    (1511, 5310611298519956951, 12208301835678061), (1523, 3355054568888736571, 12112110356999048),
    (1531, 13325995392242171187, 12048820426982071), (1543, 7651274275550300087, 11955116055547343),
    (1549, 15826806245293734085, 11908808310980988), (1553, 14028077753413380849, 11878135269613362),
    (1559, 9773579605442007463, 11832420829832938), (1567, 5579934072072959455, 11772012810280505),
    (1571, 4004035473669609867, 11742039512227594), (1579, 17874299197451307139, 11682548495066213),
    (1583, 11163601277709254863, 11653028473600474), (1597, 8663154699613126933, 11550872932817502),
    (1601, 13918592655241185729, 11522013787451312), (1607, 1503748272343466871, 11478994445369976),
    (1609, 4574425659049167865, 11464725962529242), (1613, 2904818967589724805, 11436295147991042),
    (1619, 3999263230310100443, 11393912337065813), (1621, 9707015851248764669, 11379854456329149),
    (1627, 10045368930120874451, 11337888182980670), (1637, 13127951646836669293, 11268628023035767),
    (1657, 2237655738573095881, 11132615614791521), (1663, 5291098570751326591, 11092449833860223),
    (1667, 12747839935760889899, 11065833277570216), (1669, 12312566146262696525, 11052572842246585),
    (1693, 14633182097455361973, 10895891360726256), (1697, 3782832609104846177, 10870208646853006),
    (1699, 15080946155610692875, 10857412639028576), (1709, 5137887758388383013, 10793881845353745),
    (1721, 4062356771607158665, 10718619450150814), (1723, 2141235527998787187, 10706177639993935),
    (1733, 18372233278258907149, 10644399350092066), (1741, 3401151549489239557, 10595487693112895),
    (1747, 8806287668845887835, 10559097924275644), (1753, 5387754116223211881, 10522957258248460),
    (1759, 4184338195230307615, 10487063145940620), (1777, 7816768873102584337, 10380835156842741),
    (1783, 6114428349726497479, 10345902453005917), (1787, 17001559870956704819, 10322744305377477),
    (1789, 18085851931406681685, 10311204065796283), (1801, 15916846357881534265, 10242500873797641),
    (1811, 13751024019606788891, 10185943718227251), (1823, 16463440816196072671, 10118894170987137),
    (1831, 11374316799136037015, 10074682727312698), (1847, 10307005892836089479, 9987408810887683),
    (1861, 10526836220461872013, 9912275160510237), (1867, 12903828473628641891, 9880419964493600),
    (1871, 5176130752911552431, 9859296672212480), (1873, 10567728986166763953, 9848768859428484),
    (1877, 8451891264459357693, 9827780540069020), (1879, 13538084128603231335, 9817319890212640),
    (1889, 13896091485912489121, 9765348900852065), (1901, 9383483176894863973, 9703705456975040),
    (1907, 2843913349591299515, 9673174658473807), (1913, 12053544219622027977, 9642835375697622),
    (1931, 10661090826649331747, 9552948769399042), (1933, 6680145293117788997, 9543064704453984),
    (1949, 13790100623599187637, 9464722459573910), (1951, 7043989920509285471, 9455020027529242),
    (1973, 17128451669050125981, 9349591522407274), (1979, 736378363730699635, 9321245110515185),
    (1987, 11864589293508206827, 9283716192103448), (1993, 11727057070441546361, 9255767222132238),
    (1997, 13994400236189269253, 9237227878672784), (1999, 2768395808960913199, 9227986029869710),
    (2003, 16319336244939253851, 9209557700304319), (2011, 15043590393278798931, 9172920971511462),
    (2017, 493864243916864545, 9145634146608602), (2027, 11384744369122175171, 9100515083231155),
    (2029, 5309462069515218405, 9091544639580853), (2039, 9698337247188150727, 9046956387302379),
    (2053, 11797649765601871053, 8985262578523892), (2063, 3818109413220542191, 8941708227682768),
    (2069, 3798121302755084093, 8915777705997849), (2081, 15698790847928695777, 8864365244454373),
    (2083, 13345772116697212811, 8855854092035310), (2087, 12993154666196952983, 8838880725304049),
    (2089, 7205621428505023513, 8830418417285568), (2099, 9913257415504704251, 8788348772610553),
    (2111, 6859637185154901951, 8738391318668664), (2113, 34920480972474305, 8730120243118576),
    (2129, 5588609641870672049, 8664511072667708), (2131, 16317274790681607131, 8656379199300587),
];

#[allow(dead_code)]
pub const NEXT_PRIME: u64 = 2137;