1763是质数吗,1763是什么生肖

　　

　　要检验梅森数Mp=2 p-1(其中p为素数)是否为素数，虽然可以直接分解，但是随着p的增加，Mp的位数越来越多，分解需要的时间也越来越多。有没有不分解直接检验梅森数MP是不是素数的方法？卢卡斯-莱默法则就是因为这个原因而诞生的。 　　

　　

　　卢卡斯-莱默法则：把梅森数Mp=2^p-1作为检验对象，定义数列：{L}，其中L0=4，L=((L)^2-2) mod M，这个数列的开始几项是4,14,194,37634,1416317954……。要使M (其中n=3)为素数，当且仅当L mod M =0，(其中L0=4, L=(L)^2-2，且1=i=n-2) 。的意思是：如果L能被M整除，那么M是素数，否则M是合数；反之，如果m是素数，l必须能被m整除，这个规则不仅能检验指数是素数的情况，也能检验指数不是素数的情况。 　　

　　

　　例如：对于M4=2 ^ 4-1=15，应用Lucas-Lemmer法则进行测试。因为4-2=2，所以有必要去L2看看L2 mod 15是否等于0。流程如下： 　　

　　

　　L0=4，4 mod 15=4 　　

　　

　　L1=4^2-2=14,14 mod 15=14 　　

　　

　　L2=14^2-2=194,194 mod 15=14 　　

　　

　　最终，M4=2 ^ 4-1=15不是一个素数，因为L2 mod 15=14，14不等于0。 　　

　　

　　例如：对于M5=2 5-1=31，应用卢卡斯-莱默法则进行测试。因为5-2=3，所以要去L3看看L3 mod 31是否等于0。流程如下： 　　

　　

　　L0=4，4 mod 31=4 　　

　　

　　L1=4^2-2=14,14 mod 31=14 　　

　　

　　L2=14^2-2=194,194 mod 31=8 　　

　　

　　L3=8^2-2=62,62 mod 31=0 　　

　　

　　最终，M5=2 5-1=31是一个质数，因为L3 mod 31等于0。 　　

　　

　　例3:对于M11=2 11-1=2047，使用卢卡斯-莱默法则进行检验。因为11-2=9，所以要去L9看看L9 mod 2047是否等于0。流程如下： 　　

　　

　　L0=4，4 mod 2047=4 　　

　　

　　L1=4^2-2=14,14 mod 2047=14 　　

　　

　　L2=14^2-2=194,194 mod 2047=194 　　

　　

　　l3=194^2-2=37634,37634 mod 2047=788 　　

　　

　　l4=788^2-2=620942,620942 mod 2047=701 　　

　　

　　l5=701^2-2=491399,491399 mod 2047=119 　　

　　

　　l6=119^2-2=14159,14159 mod 2047=1877 　　

　　

　　l7=1877^2-2=3523127,3523127 mod 2047=240 　　

　　

　　l8=240^2-2=57598,57598 mod 2047=282 　　

　　

　　l9=282^2-2=79522,79522 mod 2047=1763 　　

　　

　　最后因为L9=79522，而79522 mod 2047=1763，而1763不等于0，也就是说L9不能被2047整除，所以M11=2 11-1=2047不是素数。这个规则只能判断Mn是否是素数，但不能得到分解结果。我们具体分解2047: 2047=23 89，说明M11确实是一个合数。 　　

　　

　　检查M11=2 11-1=2047的过程如下所示： 　　

　　

　　 　　

　　

　　测试梅森数Mn=2 n-1是否为素数(其中n=3)的c语言程序； 　　

　　

　　//根据Lucas-Lemmer法则：Mn是素数当且仅当L可被Mn整除(其中l0=4，L=((L) 2-2) mod Mn，1=i=n-2) 　　

　　

　　#包含stdio.h 　　

　　

　　#定义N 10000 　　

　　

　　Main () //注意：使用数组的一个单元来存储9位整数。 　　

　　

　　{ void shuchu(int，无符号long long)；//输出函数原型声明 　　

　　

　　int x，I，k，lb=1，lc=1，l，ss，jw，n，g=1；//被除数单位数lb，除数单位数lc，乘积单位数L，试商ss，进位jw，指数N，测试次数G 　　

　　

　　无符号long long b={0，4}，c={0，1}，j={}，y={}，XJ；//被除数B，除数C，乘积J，余数Y，新乘积xj 　　

　　

　　Printf('请输入整数指数n:')；scanf('%d '，n)； 　　

　　

　　//a .求被测数Mn=2 n-1:这里被除数b=L( 　　

i从0到n-2),除数c=被检验数Mn，

　　

for(i=1;i<=n;i++)

　　

{ jw=0;

　　

for(k=1;k<=lc;k++)

　　

{ c=c*2+jw;

　　

if(c<=999999999)jw=0; else{jw=1;c-=1000000000;}

　　

}

　　

if(jw>=1){lc++;c=1;}

　　

}

　　

c<1>--;

　　

printf("2^%d-1=",n); //输出被检验数Mn=2^n-1：

　　

shuchu(lc,c); //调用输出函数：输出被检验数Mn的各单元

　　

//B. 检验：

　　

printf("\n检验结果如下：");

　　

printf("\nL<0>= 4");

　　

while(n!=2)

　　

{ //a.求L=L^2-2(其中i从0到n-2)：

　　

for(i=1;i<=lb;i++)

　　

{ for(k=1;k<=lb;k++) //被乘数k,乘数i

　　

{ l=k+i-1; //积的位数l

　　

j+=b*b; //求积

　　

j+=j/1000000000; //求进位

　　

j %=1000000000; //求本位

　　

}

　　

}

　　

if(j>=1) l++; //处理首位进位

　　

lb=l;j<1>-=2;

　　

//b.求s mod Mn:

　　

for(x=1;x<=lb;x++) {y=j;j=0;} //2.做除法：

　　

for(i=lb;i>=lc;i--)

　　

{ y+=y*1000000000;y=0;

　　

while(y>c)

　　

{ if(y>=18446744073) ss=y/(c+1);

　　

else ss=(y*1000000000+y)/(c*1000000000+c+1);

　　

if(ss==0) ss=1;

　　

jw=0;

　　

for(k=1;k<=lc-1;k++)

　　

{ xj=c*ss+jw;

　　

if(xj<=999999999)jw=0; else{jw=xj/1000000000;xj%=1000000000;}

　　

l=k+i-lc;

　　

if(y<xj) {y+=1000000000;y--;}

　　

y-=xj;

　　

}

　　

xj=c*ss+jw;

　　

y-=xj;

　　

}

　　

}

　　

while(y>=c)

　　

{ for(x=lc;x>=1;x--)

　　

{ if(y>c) break;

　　

if(y<c) goto tc;

　　

}

　　

for(x=1;x<=lc;x++)

　　

{ if(y<c) {y+=1000000000;y--;}

　　

y-=c;

　　

}

　　

}

　　

printf("\nL<%d>=",g); //输出余数:

　　

for(x=lc;x>=1;x--) //逐单元检查余数：

　　

{ if(y!=0||x==1) {l=x;break;}//标记非0首单元,退出

　　

}

　　

shuchu(l,y); //调用输出函数：输出余数y<>的各单元

　　

tc:

　　

//c.判断余数是否为0：

　　

for(x=lc;x>=1;x--) {if(y!=0) break;}

　　

if(x==0) {printf("\n最终因为L=L<%d>=0，所以它是素数.",g); break;} //1.余数=0时，结束验证

　　

else //2.余数!=0，继续验证：

　　

{ for(x=lc;x>=1;x--) {b=y;}//求新的被检验数：

　　

n--;g++; lb=lc;

　　

if(n==2) //直到n=2时，余数仍不为0，说明它不是素数，结束验证

　　

{ printf("\n最终因为L=L<%d>=",g-1);

　　

shuchu(lc,y); //调用输出函数：输出余数y<>的各单元

　　

printf(" 不等于0，所以它不是素数."); //余数!=0,说明Mn不是素数:结束验证

　　

}

　　

}

　　

}

　　

return 0;

　　

}

　　

//输出函数：

　　

void shuchu(int lb,unsigned long long b)

　　

{ int x;

　　

printf("%u",b); lb--; //输出首单元

　　

for(x=lb;x>=1;x--) printf(" %09u",b); //输出其余单元

　　

}

　　

检验M137=2^137-1=的过程太长，此处省略过程只把结果展示如下：