梅森素数

1.问题描述

梅森数指的是形如的正整数，其中指数n是素数，常记为，如果一个梅森数是素数，则称其为梅森素数。例如，都是梅森素数。试求出指数n<30的所有梅森素数。

2.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*求平方根*/
int isqrt(int a)
{
    int i;

    if(a == 1)
    {
        return 1;
    }

    for(i=1; i<a; i++)
    {
        if(i*i > a)
        {
            break;
        }
    }

    return i-1;
}

/*求2的n次方-1*/
int pow2sub1(int n)
{
    int a = 1;
    int i;

    for(i=0; i<n; i++)
    {
        a *= 2;
    }

    return a - 1;
}

/*判断是否为质数*/
short isPrime(int a)
{
    int u;
    int i;

    if(a == 1)
    {
        return 0;
    }

    u = isqrt(a);

    for(i=2; i<=u; i++)
    {
        if(a % i == 0)
        {
            return 0;
        }
    }

    return 1;
}

int main()
{
    int a = 0;
    int n = 31;
    int i = 0;
    int j = 1;

    for(i=1; i<n; i++)
    {
        a = pow2sub1(i);

        if(isPrime(i) && isPrime(a))
        {
            printf("M(%d)=%d\n", i, a);
        }
    }

    return 0;
}

3.编译源码

$ gcc -o test test.c -std=c89

4.运行及其结果

$ ./test
M(2)=3
M(3)=7
M(5)=31
M(7)=127
M(13)=8191
M(17)=131071
M(19)=524287