读书人

写了个求梅森素数的程序输出不正确

发布时间: 2012-05-28 17:59:33 作者: rapoo

写了个求梅森素数的程序,输出不正确,求指教

C/C++ code
#include<stdio.h>int expo = 2;int divisor = 2;int square = 0;unsigned long long MersennePrime = 3;//Mersenne prime number(2^p-1)unsigned long long MersennePrimePlus1 = 4;//Mersenne prime number plus 1 (2^p)int isPrime(unsigned long long number){    if(number ==2)    {        return 1;    }    divisor = 2;    square = (divisor) * (divisor);    while(square<=number)    {        if(number%divisor==0)        {            return 0;//Not prime, return false        }        divisor++;        square = (divisor) * (divisor);    }    return 1;//else return true}void Mersenne(int a){    if(a>=0&&a<=10)    {        unsigned long long MersennePrime = 3;        unsigned long long MersennePrimePlus1 = 4;        printf("%d mers = ",a);        expo = 2;        while(a>0)        {            if(isPrime(MersennePrime)&&isPrime(expo))            {                printf("%llu ",MersennePrime);                a--;            }            MersennePrimePlus1 = MersennePrimePlus1 * 2;            MersennePrime = MersennePrimePlus1 - 1;            expo++;        }        printf("\n");    }else    {        printf("This program can only compute up to 10 Mersenne primes\n");    }}int main(){    Mersenne(10);    getchar();    return 0;}

1到8还有第10个都是梅森素数,但是第9个不是,算了下是2^59-1,59也是素数,是我isPrime写错了么?该如何改正?谢谢
(我的思路是用求平方根限定约数的范围,但是作业要求只能用stdio.h不能用math等library,所以我就自己写了个了,思路是如果divisor的平方大于number就跳出循环,问题是所有数字都是正确的只有第9个不对,我用isPrime方法求前1000个质数,跟我用一般的方法求的答案也是对的,找了很久都找不到第9个数错的原因,只好上来求救了)

[解决办法]
#include<stdio.h>

unsigned long long expo = 2;
unsigned long long divisor = 2;
int square = 0;
unsigned long long MersennePrime = 3;//Mersenne prime number(2^p-1)
unsigned long long MersennePrimePlus1 = 4;//Mersenne prime number plus 1 (2^p)

int isPrime(unsigned long long number)
{
if(number ==2)
{
return 1;
}
divisor = 2;
square = (divisor) * (divisor);
while(square<=number)
{
if(number%divisor==0)
{
return 0;//Not prime, return false
}
divisor++;
square = (divisor) * (divisor);
}
return 1;//else return true
}

void Mersenne(int a)
{
if(a>=0&&a<=10)
{
unsigned long long MersennePrime = 3;
unsigned long long MersennePrimePlus1 = 4;
printf("%d mers = ",a);
expo = 2;
while(a>0)
{
if(isPrime(MersennePrime)&&isPrime(expo))
{
printf("%llu ",MersennePrime);
a--;
}
MersennePrimePlus1 = MersennePrimePlus1 * 2;
MersennePrime = MersennePrimePlus1 - 1;
expo++;
}
printf("\n");
}else
{
printf("This program can only compute up to 10 Mersenne primes\n");
}
}


int main(){
Mersenne(10);
getchar();
return 0;
}

读书人网 >C++

热点推荐