[C++知识库]Mersenne素数（梅森素数）C语言版

梅森数与梅森素数

梅森数(Mersenne number)又称麦森数，是指形如2^p－1的正整数，其中指数p是素数，常记为Mp 。若其是素数，则称为梅森素数。

———————注意———————

• 梅森数：满足2^p—1的所有数，梅森数可能是合数也可能是素数。
• 梅森素数：梅森数中的素数，才称之为梅森素数。

举例：2^11—1=2047=23×89，
所以2047是合数，只能称其梅森数。————————————————
梅森素数的确定：就是判断一个符合格式要求的梅森数是素数即可 。

算法：打印前n个梅森素数。（C语言版）

/* 简介：形为 Mp = 2^p-1，p为素数的数字叫做梅森数 。当梅森数Mp为素数时，叫做 Mersenne素数。*/
/*要求：计算前n个 Mersenne素数。*/
/*素数判断：除了2和3以外，质数只分布在6x(x>=1)的两侧，所以只需要判断 6x-1 与 6x+1 .*/
/*代码缺陷：只能打印前8个梅森素数。因为定义的梅森数Mp是int类型的。第九个及以后的范围超过了int类型的范围。*/
#include<stdio.h>
#include<math.h>
int Isprime(int num)//判断是否为素数，是则返回1（真），否者返回0（假） 
{
	int i;
    for (i = 2; i <= sqrt(num); i++)
    if (num % i == 0) return 0;
    return 1;
}
int main()
{
	int n;
	printf("--------------< 计算前n个Mersenne素数 >------------hao\n\n"); 
	printf("请输入n（n<=8）：");
	scanf("%d",&n);
	int count=3,p=2,x,Mp;
	printf("\ni      |p      |2^p-1  \n");
	printf("_______|_______|________\n");
	if(n>=1) printf("1      |2      |3      \n");
	if(n>=2) printf("2      |3      |7      \n");//如果n符合要求则打印前两个梅森素数 
	for(x=1;count<=n;++x)
	{
		p = 6*x-1;//6x的左侧 
		Mp=pow(2,p)-1;
        if(Isprime(p) && Isprime(Mp) &&count<=n ) //如果p为素数，梅森数Mp也为素数，则其为梅森素数。且若这是前n个梅森素数，则打印。 
        {
          printf("%-7d|%-7d|%-7d\n",count,p,Mp);
          count++;
        }
        
        p = 6*x+1;//6x的右侧 
        Mp=pow(2,p)-1;
        if( Isprime(p) && Isprime(Mp) && count<=n ) 
        {
         printf("%-7d|%-7d|%-7d\n",count,p,Mp);
         count++;
        }  		
	}
	return 0;
 } 

输入输出样例：

--------------< 计算前n个Mersenne素数 >------------hao

请输入n（n<=8）：8

i      |p      |2^p-1
_______|_______|________
1      |2      |3
2      |3      |7
3      |5      |31
4      |7      |127
5      |13     |8191
6      |17     |131071
7      |19     |524287
8      |31     |2147483647