求助

冬蕶

请用c语言编程这道题目:
编程找出无符号长整型数域范围内所有的梅森素数。

FishC

梅森素数是指形如2^p-1的素数，其中p是质数。为了找出无符号长整型数域范围内的所有梅森素数，我们需要先编写一个函数来检查一个数是否是素数，然后再使用这个函数来找到梅森素数。下面是一个解决方案：

#include <stdio.h>
#include <stdbool.h>  // 需要引入stdbool.h头文件来使用bool类型

// 检查一个数是否是素数
bool isPrime(unsigned long long int num) {
    if (num <= 1) {
        return false;
    }
  
    for (unsigned long long int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
    }
  
    return true;
}

int main() {
    unsigned long long int p = 2;  // 初始化p为2
    
    while (true) {
        unsigned long long int mersenne = (1ULL << p) - 1;  // 计算梅森素数
        
        if (mersenne > 0xFFFFFFFFFFFFFFFF || isPrime(mersenne) == false) {
            break;  // 如果梅森素数大于无符号长整型数域范围或者不是素数，退出循环
        }
        
        printf("梅森素数 M%d = %llu\n", p, mersenne);  // 输出答案
        
        p++;  // 增加p的值以寻找下一个梅森素数
    }
    
    return 0;
}

这个程序中，我们首先定义了一个`isPrime`函数，用于检查一个数是否是素数。然后在`main`函数中，我们从p=2开始逐个增加p的值，计算梅森素数，并通过调用`isPrime`函数进行验证和输出结果。当梅森素数超过无符号长整型数域范围或者不是素数时，程序会退出循环。

请注意，由于无符号长整型数域范围非常大，这个程序可能会耗费大量时间来计算和验证梅森素数。因此，请耐心等待程序运行完成。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

jackz007

#include <stdio.h>
int main(void)
{
        int c , n                                                                        ;
        unsigned long long d , i , m                                                     ;
        for(c = 0 , m = 2LL ; m ; m ++) {
                for(i = 2LL ; i * i <= m && m % i ; i ++)                                ;
                if(i * i > m) {                                                            // 如果 m 是素数
                        for(d = m + 1 , n = 0 ; d >= 2LL && ! (d % 2) ; n ++ , d /= 2LL) ; // 确定 m + 1 是否恰好是 2 的指数幂
                        if(d == 1) {                                                       // 如果 m + 1 恰好是 2 的指数幂
                                printf("%2d : %8I64u = 2 ^ %2d - 1\n" , c + 1 , m , n)   ;
                                c ++                                                     ;
                        }
                }
        }
}

        编译、运行实况：

D:\[exercise]\C>g++ -o ms ms.c

D:\[exercise]\C>ms
 1 :        3 = 2 ^  2 - 1
 2 :        7 = 2 ^  3 - 1
 3 :       31 = 2 ^  5 - 1
 4 :      127 = 2 ^  7 - 1
 5 :     8191 = 2 ^ 13 - 1
 6 :   131071 = 2 ^ 17 - 1
 7 :   524287 = 2 ^ 19 - 1

        此程序循环非常耗时，需要耐心等待才能正常结束。

jackz007

#include <stdio.h>

/*
   在无符号长整型数范围内，找出所有的梅森素数
----------------------------------------------------
   梅森素数：x = 2 ^ n - 1，如果 x 和 n 都是素数，
   那么，x 就是一个梅森素数。
*/

unsigned long long max(void)                                                             // 为了防止 k * k 发生溢出，需要确定出 k 值上限
{
        unsigned long long k                                                            ;
        for(k = 1LL ; 0xffffffffffffffffLL / k >= k ; k ++)                             ;
        return k                                                                        ;
}

int main(void)
{
        unsigned long long d , e , k                                                    ;
        int c , n , p                                                                   ;
        e = max()                                                                       ; // e 为 unsigned long long 型可搜索因子的上限值
        for(c = 0 , n = 2 ; n < 64 ; n ++) {                                              // n 在 2 ~ 63 范围内循环
                for(p = 2 ; p * p <= n && n % p ; p ++)                                 ; 
                if(p * p > n) {                                                           // 如果 n 是素数
                        d = (1LL << n) - 1LL                                            ; // d = 2 ^ n - 1
                        for(k = 2LL ; k < e && k * k <= d && d % k ; k ++)              ;  
                        if(k >= e || k * k > d) {                                         // 如果 d 是素数
                                printf("%2d : %20I64u = 2 ^ %2d - 1\n" , c + 1 , d , n) ;
                                c ++                                                    ;
                        }                                             
                }
        }
}

        编译、运行实况：

D:\[exercise]\C>g++ -o x x.c

D:\[exercise]\C>x
 1 :                    3 = 2 ^ 2 - 1
 2 :                    7 = 2 ^ 3 - 1
 3 :                   31 = 2 ^ 5 - 1
 4 :                  127 = 2 ^ 7 - 1
 5 :                 8191 = 2 ^ 13 - 1
 6 :               131071 = 2 ^ 17 - 1
 7 :               524287 = 2 ^ 19 - 1
 8 :           2147483647 = 2 ^ 31 - 1
 9 :  2305843009213693951 = 2 ^ 61 - 1

D:\[exercise]\C>

         在64位无符号长整型范围内，一共可以找到9个梅森素数