求助

冬蕶

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

FishC

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

1. #include <stdio.h>
   
2. #include <stdbool.h>  // 需要引入stdbool.h头文件来使用bool类型
   
3. 
   
4. // 检查一个数是否是素数
   
5. bool isPrime(unsigned long long int num) {
   
6.     if (num <= 1) {
   
7.         return false;
   
8.     }
   
9.   
   
10.     for (unsigned long long int i = 2; i * i <= num; i++) {
    
11.         if (num % i == 0) {
    
12.             return false;
    
13.         }
    
14.     }
    
15.   
    
16.     return true;
    
17. }
    
18. 
    
19. int main() {
    
20.     unsigned long long int p = 2;  // 初始化p为2
    
21.    
    
22.     while (true) {
    
23.         unsigned long long int mersenne = (1ULL << p) - 1;  // 计算梅森素数
    
24.         
    
25.         if (mersenne > 0xFFFFFFFFFFFFFFFF || isPrime(mersenne) == false) {
    
26.             break;  // 如果梅森素数大于无符号长整型数域范围或者不是素数，退出循环
    
27.         }
    
28.         
    
29.         printf("梅森素数 M%d = %llu\n", p, mersenne);  // 输出答案
    
30.         
    
31.         p++;  // 增加p的值以寻找下一个梅森素数
    
32.     }
    
33.    
    
34.     return 0;
    
35. }

复制代码

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

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

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

jackz007

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

复制代码

        编译、运行实况：

1. D:\[exercise]\C>g++ -o ms ms.c
   
2. 
   
3. D:\[exercise]\C>ms
   
4. 1 :        3 = 2 ^  2 - 1
   
5. 2 :        7 = 2 ^  3 - 1
   
6. 3 :       31 = 2 ^  5 - 1
   
7. 4 :      127 = 2 ^  7 - 1
   
8. 5 :     8191 = 2 ^ 13 - 1
   
9. 6 :   131071 = 2 ^ 17 - 1
   
10. 7 :   524287 = 2 ^ 19 - 1
    

复制代码

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

jackz007

1. #include <stdio.h>
   
2. 
   
3. /*
   
4.    在无符号长整型数范围内，找出所有的梅森素数
   
5. ----------------------------------------------------
   
6.    梅森素数：x = 2 ^ n - 1，如果 x 和 n 都是素数，
   
7.    那么，x 就是一个梅森素数。
   
8. */
   
9. 
   
10. unsigned long long max(void)                                                             // 为了防止 k * k 发生溢出，需要确定出 k 值上限
    
11. {
    
12.         unsigned long long k                                                            ;
    
13.         for(k = 1LL ; 0xffffffffffffffffLL / k >= k ; k ++)                             ;
    
14.         return k                                                                        ;
    
15. }
    
16. 
    
17. int main(void)
    
18. {
    
19.         unsigned long long d , e , k                                                    ;
    
20.         int c , n , p                                                                   ;
    
21.         e = max()                                                                       ; // e 为 unsigned long long 型可搜索因子的上限值
    
22.         for(c = 0 , n = 2 ; n < 64 ; n ++) {                                              // n 在 2 ~ 63 范围内循环
    
23.                 for(p = 2 ; p * p <= n && n % p ; p ++)                                 ;
    
24.                 if(p * p > n) {                                                           // 如果 n 是素数
    
25.                         d = (1LL << n) - 1LL                                            ; // d = 2 ^ n - 1
    
26.                         for(k = 2LL ; k < e && k * k <= d && d % k ; k ++)              ;  
    
27.                         if(k >= e || k * k > d) {                                         // 如果 d 是素数
    
28.                                 printf("%2d : %20I64u = 2 ^ %2d - 1\n" , c + 1 , d , n) ;
    
29.                                 c ++                                                    ;
    
30.                         }                                             
    
31.                 }
    
32.         }
    
33. }

复制代码

        编译、运行实况：

1. D:\[exercise]\C>g++ -o x x.c
   
2. 
   
3. D:\[exercise]\C>x
   
4. 1 :                    3 = 2 ^ 2 - 1
   
5. 2 :                    7 = 2 ^ 3 - 1
   
6. 3 :                   31 = 2 ^ 5 - 1
   
7. 4 :                  127 = 2 ^ 7 - 1
   
8. 5 :                 8191 = 2 ^ 13 - 1
   
9. 6 :               131071 = 2 ^ 17 - 1
   
10. 7 :               524287 = 2 ^ 19 - 1
    
11. 8 :           2147483647 = 2 ^ 31 - 1
    
12. 9 :  2305843009213693951 = 2 ^ 61 - 1
    
13. 
    
14. D:\[exercise]\C>

复制代码

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