一个素数的问题~ - C语言论坛

楼主

已结贴√ 问题点数：20 回复次数：27

一个素数的问题~

i为要验证的数，用for(j=2;j<=i/2;j++)这种形式来验证素数时，能不能改为j<i/2? 理论上是可以的，用数学知识都可以验证，但c语言上却有差别，做机试时电脑会认为后者错。这是为什么？

搜索更多相关主题的帖子: 素数　

第 2 楼

得分:2

试试i=4会发生什么

C/C++算法群19472277

第19次算法竞赛http://

第 3 楼

得分:2

其实在理论上，只有当i>4的时候，你这判断的方式才算完全正确。。。
这里必须保证i/2大于根号i时，即i>4时才成立。
比如i=3，或者i=4，时你用j<i/2,得到的是2<3/2或2<4/2,这时电脑自然会报错。。

第 4 楼

得分:2

程序代码：

bool IsPrime(int n)
{
    if( n==2||n==3||n==5)
        return true;
    if(( (n-1)%6==0 ||(n-5)%6==0)&& n>=7)
    {
        for(int i=2;i<=sqrt(n);i++)
            if( n % i == 0 )
                return false;
        return true;
    }
    return false;
}

这才是素性判别的典范。

第 5 楼

得分:2

要是求 100--1000内的素数的话
偶会这样for(j = 2; j < i/2 + 10; j++)

我就是真命天子，顺我者生，逆我者死！

第 6 楼

得分:0

以下是引用Devil_W在2009-9-17 10:45的发言：

bool IsPrime(int n)
{
    if( n==2||n==3||n==5)
        return true;
    if(( (n-1)%6==0 ||(n-5)%6==0)&& n>=7)
    {
        for(int i=2;i<=sqrt(n);i++)
            if( n % i == 0 )
                return false;
        return true;
    }
    return false;
}

这才是素性判别的典范。

写得混乱+低效

C/C++算法群19472277

第19次算法竞赛http://