求助
请用c语言编程这道题目:编程找出无符号长整型数域范围内所有的梅森素数。 梅森素数是指形如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 于 2024-4-12 00:22 编辑
#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:\\C>g++ -o ms ms.c
D:\\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 于 2024-4-12 10:28 编辑
#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:\\C>g++ -o x x.c
D:\\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:\\C>
在64位无符号长整型范围内,一共可以找到9个梅森素数
页:
[1]