梅森素数：nefu 120 梅森素数（卢卡斯—莱默判别法+大数乘积取模

发布时间：2020-12-14 02:49:26 所属栏目：大数据来源：网络整理

导读：梅森素数 description 由于梅森学识渊博，才华横溢，为人热情以及最早系统而深入地研究2 p －1 型的数（其中p为素数），为了纪念他，数学界就把这种数称为“梅森数”；并以M p 记之（其中M为梅森姓名的首字母），即M p =2 p -1 。如果梅森数为素数，则称之为

梅森素数

description

由于梅森学识渊博，才华横溢，为人热情以及最早系统而深入地研究2^p－1 型的数（其中p为素数），为了纪念他，数学界就把这种数称为“梅森数”；并以M_p 记之（其中M为梅森姓名的首字母），即M_p=2^p-1 。如果梅森数为素数，则称之为“梅森素数”。 比如p＝2，3，5，7时，M_p都是素数，但2¹¹-1 不是素数 。现在请你求出前N个梅森素数。

input

有多组测试数据。
第一行是一个正整数T，表示测试数据的组数。接下来每组1个数p的值，这里2&lt;= p &lt;= 62。

output

对于每组测试数据，判断M_p 是不是梅森素数，是就输出“yes ”，否就输出“no”，输出后要换行。

sample_input

2
2
7

sample_output

yes
yes

解题思路：

1.梅森素数的判定方法之一——Lucas—Lehmer判别法：

构造rk序列判断Mp是否是素数，同时应用大数乘积取模的算法，将乘法变成加法

参考代码+部分解释：

2.枚举判断——梅森素数表

附表：梅森素数表（1-47个）

序号	p	Mp=（2^p）-1	Mp的位数	发现时间	发现者
1	2	3	1	古代	古人
2	3	7	1	古代	古人
3	5	31	2	古代	古人
4	7	127	3	古代	古人
5	13	8191	4	1456年	无名氏
6	17	131071	6	1588年	Cataldi
7	19	524287	6	1588年	Cataldi
8	31	2147483647	10	1772年	欧拉
9	61	2305843009213693951	19	1883年	Pervushin
10	89	618970019642690137449562111	27	1911年	Powers
11	107	162259276829213363391578010288127	33	1914年	Powers
12	127	170141183460469231731687303715884105727	39	1876年	卢卡斯
13	521	686479766013060971498190079908139321726 943530014330540939446345918554318339765 605212255964066145455497729631139148085 803712198799971664381257402829111505715 1	157	1952年1月30日	Robinson
14	607	531137992816767098689588206552468627329 593117727031923199444138200403559860852 242739162502265229285668889329486246501 015346579337652707239409519978766587351 943831270835393219031728127	183	1952年1月30日	Robinson
15	1279	104079321946643990819252403273640855386 152622472667048053191123504036080596733 602980122394417323241848424216139542810 077913835662483234649081399066056773207 629241295093892203457731833496615835504 729594205476898112116936771475484788669 625013844382602917323488853111608285384 165850282556046662248318909188018470682 222031405210266984354887329580288780508 69736186900714720710555703168729087	386	1952年6月25日	Robinson
16	2203	147597991521418023508489862273738173631 206614533316977514777121647857029787807 894937740733704938928938274850753149648 047728126483876025919181446336533026954 049696120111343015690239609398909022625 932693502528140961498349938822283144859 860183431853623092377264139020949023183 644689960821079548296376309423663094541 083279376990539998245718632294472963641 889062337217172374210563644036821845964 963294853869690587265048691443463745750 728044182367681351785209934866084717257 940842231667809767022401199028017047489 448742692474210882353680848507250224051 945258754287534997655857267022963396257 521263747789778550155264652260998886991 401354048380986568125041949768669777100 7	664	1952年10月7日	Robinson
17	2281	446087557183758429571151706402101809886 208632412859901111991219963404685792820 473369112545269003989026153245931124316 702395758705693679364790903497461147071 065254193353938124978226307947312410798 874869040070279328428810311754844108094 878252494866760969586998128982645877596 028979171536962503068429617331702184750 324583009171832104916050157628886606372 145501702225925125224076829605427173573 964812995250569412480720738476855293681 666712844831190877620606786663862190240 118570736831901886479225810414714078935 386562497968178729127629594924411960961 386713946279899275006954917139758796061 223803393537381034666494402951052059047 968693255388647930440925104186817009640 171764133172418132836351	687	1952年10月9日	Robinson
18	3217	259117086013202627776246767922441530941 818887553125427303974923161874019266586 362086201209516800483406550695241733194 177441689509238807017410377709597512042 313066624082916353517952311186154862265 604547691127595848775610568757931191017 711408826252153849035830401185072116424 747461823031471398340229288074545677907 941037288235820705892351068433882986888 616658650280927692080339605869308790500 409503709875902119018371991620994002568 935113136548829739112656797303241986517 250116412703509705427773477972349821676 443446668383119322540099648994051790241 624056519054483690809616061625743042361 721863339415852426431208737266591962061 753535748892894599629195183082621860853 400937932839420261866586142503251450773 096274235376822938649407127700846077124 2118230808041392980870575047138252645714 4837937112503208182612656664908425169945 3951887789613650248405739378594599444335 2311882801236604062624686092121503499375 8478229223714433962885848593821573882123 2393687046160677362909315071	969	1957年9月8日	Riesel
19	4253	1907970075244390738074680429695291736693 5699474994017739474188267352897978700505 3706368049835514900244303495954950709725 7621863112241488288119202169045422069607 4466616936422119528953843684539025016866 3932838805192055137154390912666527533007 3092926875390922570433625178573666246999 7540237546295449029325923330313733064353 1556539739921926201438606439020075174723 0290568382725050515719675946083500634044 9597766065626902082396082556701234418990 8927956646011998057988548630107637380993 5198265823897818881357054086530452196558 0175808125116408055460905746802820330871 8724654081055323215860189611391296030471 1084431467456719677663089258585472715073 1156376517100831824864711009761489031356 2856541784154881743146033909602737947385 0553559603318556145409000814563786590683 7031726769698000118775099549109035010841 7050917991562167972281070161305972518044 8720483313063837150948549384157385498946 0607072258473797817668642213435452698944 3028353644037187375385397838259511833166 4161343236956603676768977222879187734209 6898232608902615003151542416546211133752 7431154890666327374921446276833564519776 7976338755035486650939145564820314822488 8312702377703966770797655985733335701372 7342079099064400455741830654320379350833 2362458193488240647835856929248810219783 3297494990612266442137603468781535048499 1	1,281	1961年11月3日	Hurwitz
20	4423	2855425422282796139015635661021640083261 6423864470288919924745660228440039060065 3875954571505539843239754513915896150297 8783993770560714351697472211079887911982 0098847753133921428277201605900990458668 6254989084815735422480409022344297588352 5260043838906326161240763173874168811485 9248618836187390417578314569601691957439 0765598280188599035578448591077683677175 5204340742877265780062667596159707595213 2782855566278167838569158184443644481251 1562428136742490459363212810180276096088 1114010033775703635457251209240736469215 7679714619938761929656030268026179011813 2925012323046444438622308877924609373773 0124816816724244936744744885377701557830 0688085264816151306714481479028836666406 2257274665275787127374649231096375001170 9018907862633246195787957314256938050730 5611967758033808433338198750090296883193 5913095269821311141322393356490178488728 9822881562826008138312961436638459454311 4404375382154287127774560644785856415921 3328443580206422714694913091762716447041 6896780700967735904298089096167504529272 5800084350034483162829708990272864998199 4387647234574276263729694848304750917174 1861811306885187927486226122933413689280 5663438446664632657247616727566083910565 0528975713899320211121495795311427946254 5533053870678210676017687509778661004600 1460213840844802122505368905479374200309 5722096732954750721718115531871310231057 902608580607	1,332	1961年11月3日	Hurwitz
21	9689	478220278…225754111	2,917	1963年5月11日	Gillies
22	9941	346088282…789463551	2,993	1963年5月16日	Gillies
23	11213	281411201…696392191	3,376	1963年6月2日	Gillies
24	19937	431542479…968041471	6,002	1971年3月4日	布莱恩特·塔克曼
25	21701	448679166…511882751	6,533	1978年10月30日	Noll& Nickel
26	23209	402874115…779264511	6,987	1979年2月9日	Noll
27	44497	854509824…011228671	13,395	1979年4月8日	Nelson& Slowinski
28	86243	536927995…433438207	25,962	1982年9月25日	Slowinski
29	110503	521928313…465515007	33,265	1988年1月28日	Colquitt& Welsh
30	132049	512740276…730061311	39,751	1983年9月20日	Slowinski
31	216091	746093103…815528447	65,050	1985年9月6日	Slowinski
32	756839	174135906…544677887	227,832	1992年2月19日	Slowinski& Gage
33	859433	129498125…500142591	258,716	1994年1月10日	Slowinski& Gage
34	1257787	412245773…089366527	378,632	1996年9月3日	Slowinski& Gage
35	1398269	814717564…451315711	420,921	1996年11月13日	GIMPS/Joel Armengaud
36	2976221	623340076…729201151	895,932	1997年8月24日	GIMPS/Gordon Spence
37	3021377	127411683…024694271	909,526	1998年1月27日	GIMPS/Roland Clarkson
38	6972593	437075744…924193791	2,098,960	1999年6月1日	GIMPS/Nayan Hajratwala
39	13466917	924947738…256259071	4,053,946	2001年11月14日	GIMPS/Michael Cameron
40	20996011	125976895…855682047	6,320,430	2003年11月17日	GIMPS/Michael Shafer
41	24036583	299410429…733969407	7,235,733	2004年5月15日	GIMPS/Josh Findley
42*	25964951	122164630…577077247	7,816,230	2005年2月18日	GIMPS/Martin Nowak
43*	30402457	315416475…652943871	9,152,052	2005年12月15日	GIMPS/Curtis Cooper及Steven Boone
44*	32582657	124575026…053967871	9,808,358	2006年9月4日	GIMPS/Curtis Cooper及Steven Boone
45*	37156667	202254406…308220927	11,185,272	2008年9月6日	GIMPS/Hans-Michael Elvenich
46*	42643801	169873516…562314751	12,837,064	2009年4月12日	GIMPS/Odd M. Strindmo
47*	43112609	316470269…697152511	12,978,189	2008年8月23日	GIMPS/Edson Smith

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!