求优化觅素数代码

求优化找素数代码
[yabao=][/yabao]

#include <iostream>
#include <math.h>
using namespace std;
bool isPrime(long number)
{
    bool primeNumber=true;
    if(number==2)  primeNumber=true;
    if(number%2==0) primeNumber=false;
    for(int i=3;i<=sqrt(number);i+=2)
    {
        //if(isPrime(i))
        {
            if(number%i==0)
                primeNumber=false;
            else
                primeNumber=true;
        }
    }
    return primeNumber;
}

int main()
{
    cout<<isPrime(400000000000000001);
}

最开始没有注释的那句话，我先排除2的倍数，然后是从3开始到根号n的奇数，加上注释那句话，我先排除2的倍数，然后是从3开始到根号n的质数，按理说，后者应该比较快，因为不用再去考虑9，15，21这样的奇数非质数，但因为是递归调用，反而比第一种情况慢，求优化！！thanx
[解决办法]

引用:

引用:cout<<isPrime(400000000000000001);是不是考虑下形参的取值范围呢
我想到取值范围了，在我电脑上能运行，我64位的，没有报错呀。

能用循环尽量用循环，不要用递归，递归付出的代价比循环大。
[解决办法]
如果你要判断的数在某个范围内，你可以先打一个该范围内的素数表。。
否则你这样为了排除某些奇合数，只是省了模运算而多了一次甚至更多次的函数调用，是绝对得不偿失的。
[解决办法]
你这算法无论怎么搞，效率都高不到哪去，这是找素数的效率最最最低的算法！

真正应用的算法，是 Lehmann's Primality Test，Miller-Rabin Primality Test  这样的

即使要判断某个范围内的，也要用 Sieve of Eratosthenes 方法

查看更多 下一篇