#include stdio.h
庐阳网站建设公司创新互联建站,庐阳网站设计制作,有大型网站制作公司丰富经验。已为庐阳上千多家提供企业网站建设服务。企业网站搭建\成都外贸网站建设要多少钱,请找那个售后服务好的庐阳做网站的公司定做!
#define true 1
#define false 0
long isprime(int n);
long mypow(int m, int n);
int main()
{
int n,a;
for(n=2;n20;n++)
{
a = mypow(2,n)+1;
if(isprime(n)isprime(a))
{
printf("%d是梅森素数\n", a);
}
}
return 0;
}
long mypow(int m, int n) {
long ans = 1;
int i = 0;
for (; i n; i++) {
ans *= m;
}
return ans;
}
long isprime(int n) {
int x = 0;
if (n 2) return false;
if (n == 2|| n==3) {
return true;
}
// 6x 6x+1 6x+2 6x+3 6x+4 6x+5
// 6x+2 = 2(3x+1)
// 6x+3 = 3(2x+1)
// 6x+4 = 2(3x+2)
if (n % 6 != 1 n % 6 != 5) {
return false;
}
for (x = 5; x * x = n; x += 6) {
if (n % x == 0 || n % (x+2) == 0) {
return false;
}
}
return true;
}
形如2^p-1的正整数,其中p是素数,常记为Mp 。若Mp是素数,则称为梅森素数。梅森素数貌似简单,而研究难度却很大。它不仅需要高深的理论和纯熟的技巧,而且需要进行艰巨的计算。即使属于“猜测”部分中最小的M31=2147483647,也具有10位数。可以想象,它的证明是十分艰巨的。正如梅森推测:“一个人,使用一般的验证方法,要检验一个15位或20位的数字是否为素数,即使终生的时间也是不够的。
迄今为止,人类仅发现48个梅森素数。由于这种素数珍奇而迷人,它被人们称为“数学珍宝”。梅森素数历来是数论研究的一项重要内容,也是当今科学探索的热点和难点之一。
值得一提的是:在梅森素数的基础研究方面,法国数学家鲁卡斯和美国数学家雷默都做出了重要贡献;以他们命名的“鲁卡斯-雷默方法”是目前已知的检测梅森素数素性的最佳方法。此外,中国数学家和语言学家周海中给出了梅森素数分布的精确表达式,为人们寻找梅森素数提供了方便;这一研究成果被国际上命名为“周氏猜测”。
程序:
#include stdio.h
int prime(unsigned long v)
{
unsigned long i;
for(i = 3; i = v/2; i +=2)
if(v % i == 0) return 0;
return 1;
}
int main()
{
int i;
unsigned long v;
printf("p\t2^p-1\n");
for(i = 2; i 32; i ++)
{
v = (1i)-1;
if(prime(v))
printf("%d\t%lu\n",i, v);
}
return 0;
}
输出
p 2^p-1
2 3
3 7
5 31
7 127
13 8191
17 131071
19 524287
31 2147483647
古希腊数学家欧几里得在名著《几何原本》中证明了素数有无穷多个,并论述完全数时提出:如果2^P-1是素数(其中指数P也是素数),则2^(P-1)(2^P-1)是完全数。瑞士数学家和物理学家欧拉证明所有的偶完全数都有这种形式。因此,人们只要找到2^P-1型素数,就可以发现偶完全数了。数学界将2^P-1型素数称为“梅森素数”(Mersenne prime),因为法国数学家和法兰西科学院奠基人梅森在这方面的研究成果较为卓著。梅森素数貌似简单,但探究难度却极大。它不仅需要高深的理论和纯熟的技巧,而且还需要进行艰巨的计算。到2013年2月6日为止,人类仅发现48个梅森素数。
值得提出的是:在梅森素数的基础研究方面,法国数学家鲁卡斯和美国数学家雷默都做出了重要贡献;以他们命名的“鲁卡斯-雷默方法”是目前已知的检测梅森素数素性的最佳方法。此外,中国数学家和语言学家周海中给出了梅森素数分布的精确表达式,为人们寻找梅森素数提供了方便;这一研究成果被国际上命名为“周氏猜测”。 1……6
2……28
3……496
4……8,128
5……33,550,336
6……8,589,869,056
7……137,438,691,328
8……2,305,843,008,139,952,128
9……2,658,455,991,569,831,744,654,692,615,953,842,176
10……191,561,942,608,236,107,294,793,378,084,303,638,130,997,321,548,169,216
11……13,164,036,458,569,648,337,239,753,460,458,722,910,223,472,318,386,943,117,783,728,128
12……14,474,011,154,664,524,427,946,373,126,085,988,481,573,677,491,474,835,889,066,354,349,131,199,152,128
……
……
47 ……2^42643800 X (2^42643801-1)
48 ……2^57885160 X (2^57885161-1)
由于后面数字位数较多,例子只列到12个,第13个有314位。
到第39个完全数有25674127位数,据估计它以四号字打出时需要一本字典大小的书。
梅森数(Mersenne number)是指形如2^p-1的正整数,其中指数p是素数,常记为Mp 。若Mp是素数,则称为梅森素数(Mersenne prime)。
而卢卡斯数有:1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...... (OEIS A000204),当中的平方数只有 1 和 4,这是由哥恩 (John H. E. Cohn) 证明的。而素数,即卢卡斯素数 (Lucas Prime) 则有: 3, 7, 11, 29, 47, ......
如果一个数不是1和4,而又是卢卡斯数的话就一定是梅森数