有必要这样用埃氏筛法吗?

Question

判断一个数是否质数，可以这样用埃氏筛法吗？还可以怎样优化？

bool isprime(int x)
{
    int a=ceil(sqrt(x));
    int i=2;
    bool isp;
    for(;i<=a;i++)
    {
        isp=true;
        for(int j=2;j<ceil(i/2);j++)
        {
            if(i%j==0)
                isp=false;
        }
        if(isp)
            if(x%i==0)
                return false;
    }
    return true;
}

Answer 1

呃，程序跑着没问题，不过我个人觉得不能算是埃氏筛法，可能是你在第十行那个循环那想先筛去一部分，可是第十行那个循环本身有问题，程序跑出来结果对还是靠后面那个循环，比如以100为例，第十行“筛选”后交给下面循环如图，根本就是完全靠if（isp）在计算，而且计算量远大于一般算法，埃氏算法就在csdn能找到，我就不发了，在循环计算前把它筛去，不让他参加计算，这才是这个算法优化的地方。你的代码用第十行循环和不用的运行时间如下（以1000为例）