2 xwinterwinterwinterx XwinterwinterwinterX 于 2016.04.13 18:33 提问

请教大家一段查找素数的代码
 #include<iostream>
#include<cmath>
using namespace std;
bool Jude(int n)
{
    int i;
    if(n==2||n==3)
        return true;
    else if(n<2)
        return false;
    else
    {



        for(i=2;i<=sqrt(1.0*n);i++)//这里sqrt(1.0*n)就算了一次,
        //如果判断条件改为i*i<=n,这里的i*i就会做sqrt(n)次,每次循环都要算一次,会超时
            if(n%i==0)
                return false;
        return true;



    }
}
int main()
{
    int t,a;
    int sum;
    while(~scanf("%d",&t))
    {
        sum=0;
        while(t--)
        {
            scanf("%d",&a);
            if(Jude(a)) 
                sum++;
        }
        printf("%d\n",sum);
    }
    return 0;
}

        for(i=2;i<=sqrt(1.0*n);i++)//这里sqrt(1.0*n)就算了一次,
        //如果判断条件改为i*i<=n,这里的i*i就会做sqrt(n)次,每次循环都要算一次,会超时
            if(n%i==0)
                return false;
        return true;

sqrt(1.0*n)
这里为什么要用这样写?

4个回答

u013189927
u013189927   2016.04.13 22:03
已采纳

这样写会减少计算的次数,n越大,减少的幅度越大,提高效率。

XwinterwinterwinterX
XwinterwinterwinterX   2016.04.13 18:34
VisualEleven
VisualEleven   Ds   Rxr 2016.04.14 16:50

转成dobule类型~

NK_test
NK_test   Rxr 2016.04.15 00:39

我觉得说的没啥道理,sqrt也是每次都要重新计算的,真的会超时么,你去提交下看看。。。

Csdn user default icon
上传中...
上传图片
插入图片