C语言实现梅森素数的判断与输出 - 算法解析 - 常规

C语言实现梅森素数的判断与输出 - 算法解析

题目： 梅森素数是指等于2的整数次幂减1的素数。例如：7是梅森素数，它等于2的3次方减1。示例程序为输出100以内的梅森素数，运行结果如样张所示。

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

int  msprime(int  m )
{
    int i = 2,k,p;
    while ( i <= m && (m%i))
        i++;

	 if(m==i)
    {
        for(k=1;;k++)
        {
            p=pow(2,k)-1;
            if(p>m)
                break;
            else if(p==m)
                return k;
        }
    }
    return  0;
}

int main()
{
    int m,k; 
    for(m=2;m<=100;m++)
        if (k=msprime(m))
            printf('%d=2^%d-1\n',m,k);
    return 0;
}

分析：

#include <stdio.h>：引入标准输入输出库函数，用于实现基本输入输出功能，例如 printf 和 scanf。
#include <string.h>：引入字符串处理库函数，用于处理字符串，例如 strcpy 和 strlen。
#include <ctype.h>：引入字符处理库函数，用于处理字符，例如 isalpha 和 isdigit。
#include <math.h>：引入数学库函数，用于实现数学运算，例如 pow 和 sqrt。
int msprime(int m)：定义函数 msprime，参数为 m，返回值为整型，用于判断 m 是否为梅森素数。
int i=2,k,p;：定义整型变量 i、k、p，初始值分别为 2、0、0。其中 i 用于判断素数，k 用于记录梅森素数的指数，p 用于计算 2 的 k 次方减 1 的值。
while ( i <= m && (m%i)) i++;：循环遍历 2 到 m 之间的数字，如果 m 对 i 取模不为 0，则 i 自增 1。该循环用于判断 m 是否为素数。
if(m==i)：如果 m 等于 i，则 m 是素数，进入判断梅森素数的循环。
for(k=1;;k++)：定义循环变量 k，初始值为 1，循环条件为无限循环，用于判断 2 的 k 次方减 1 是否等于 m。
p=pow(2,k)-1;：计算 2 的 k 次方减 1 的值，赋给变量 p。
if(p>m) break;：如果 p 大于 m，则说明 2 的 k 次方减 1 大于 m，退出循环。
else if(p==m) return k;：如果 p 等于 m，则说明 m 是梅森素数，返回 k 的值。
return 0;：如果没有找到符合条件的 k 值，返回 0，表示 m 不是梅森素数。
int main()：主函数，程序的入口。
int m,k;：定义整型变量 m 和 k，m 用于循环遍历，k 用于存储 msprime 函数的返回值。
for(m=2;m<=100;m++)：循环遍历 2 到 100 之间的数字，判断每个数字是否为梅森素数。
if (k=msprime(m))：如果 msprime(m) 的返回值不为 0，则说明 m 是梅森素数，将返回值赋给 k。
printf('%d=2^%d-1\n',m,k);：输出 m 和 k 的值，表示 m 是 2 的 k 次方减 1 的梅森素数。
return 0;：程序正常结束。

该程序使用了 pow 函数来计算 2 的 k 次方，并通过循环判断 2 的 k 次方减 1 是否等于 m。程序的逻辑清晰，代码易于理解，能够正确输出 100 以内的所有梅森素数。