如何用c语言写梅森数

梅森数是一个形如\(2^p - 1\)的素数，其中\(p\)也是质数。在C语言中编写一个检测梅森数的程序通常涉及两个步骤：首先找到所有可能的\(p\)值，然后检查每个\(2^p - 1\)是否为素数。

下面是一个简单的示例，使用了埃拉托斯特尼筛法（Sieve of Eratosthenes）寻找质数，然后对每个找到的\(p\)测试梅森数：

#include <stdio.h>
#include <stdbool.h>

bool is_prime(int n) {
    if (n <= 1) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    int sqrt_n = (int)sqrt(n);
    for (int i = 5; i <= sqrt_n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

bool is_mersenne_prime(int p) {
    int mersenne_num = 1 << p - 1;
    return is_prime(mersenne_num);
}

int main() {
    int max_p = 100; // 或者设定更高的上限，这取决于你想要搜索的最大梅森数位置
    for (int p = 2; ; p++) { // 从2开始寻找质数
        if (is_prime(p)) {
            long long mersenne_num = 1LL << p - 1; // 将p转换为32位整数可能会溢出，所以使用long long
            if (mersenne_num > INT_MAX) break; // 如果计算结果超出了int范围，则停止搜索

            if (is_mersenne_prime(p))
                printf("Mersenne prime found at position %d: 2^%d - 1\n", p, p);
        }
    }

    return 0;
}