超超超生手发一个自编找素数的代码，请大牛过目看看哪里可以优化，求扔砖

2013-03-27

超超超新手发一个自编找素数的代码，请大牛过目看看哪里可以优化，求扔砖谢过啦~！c++vector优化[解决办法]楼

超超超新手发一个自编找素数的代码，请大牛过目看看哪里可以优化，求扔砖

谢过啦~！ c++ vector 优化
[解决办法]
楼主可以参考下：http://blog.csdn.net/program_think/article/details/7032600
[解决办法]
算法的优化我就不说了，google一下，多成马了。
对于你的代码，我提几个建议：
1、main里面的for循环中的if语句，你的意思是用来换行。
建议：如果是对同一个变量的if判断，请用if...elseif等结构。虽然有些项目开了优化，编译器对于一些代码能自行帮你优化，但是还是养成手动优化的习惯！
2、对于CalcPrimes这个函数，除非你换思路，这样写的话，瓶颈一定在vector的push_back上。如果追求速度，请不要使用vector，直接用数组吧。
3、如果你不知道怎么优化，建议看下怎么使用VS的性能分析器，先学会怎么找到性能瓶颈再说
[解决办法]

引用

for(int i=2; i<max;i++)
    {
        int key = 0;                 //因为用这个Key保证了每个数（n）都是从2开始通过下面的循环被2至n的数全部验证了一遍。如果n是素数那么它一定不能被[2，n-1]的所有数整除。

        for (int j=2; j<i;j++)
        {
            if(i!=j && i%j != 0)
            {
                key++;               //这里可以看到，这个Key其实就是一个计数器，它记录了N以下不能将N整除的数的个数。
            }
            if(key == i-2)           //如果Key的个数一旦满足[2,n-1]之间所有数字的个数即n-2，则现在的n就是一个素数。
            {
                Primes.push_back(i);    //利用Vector<T>.push_back()函数，将素数加入容器末端。
            }
        }
    }

这段代码效率低了些。
1，首先说你的计数方法，为何不改成遇到能整除的数就判断为非素数，立即break内循环，减少循环次数，省去计数过程。
2，还有就是for (int j=2; j<i;j++)，可改为：for (int j=2; j<=i/2;j++) ，一个整数N不可能被大于N/2的整数整除。大大节约了循环次数

[解决办法]

引用:

引用for(int i=2; i<max;i++)
    {
        int key = 0;                 //因为用这个Key保证了每个数（n）都是从2开始通过下面的循环被2至n的数全部验证了一遍。如果n是素数那么它一定不能被[2，n-1]的所有数整除。

        for (int j=2; j<i;j++)
     ……

改为j<=sqrt(i)
更快.
另外,可以去看下什么素数筛选法(算法导论里有)
[解决办法]
Finding prime numbers - Kenneth Haugland
Different schemas for finding prime numbers explained with code
http://www.codeproject.com/Article.aspx?tag=198374988322054872&

热点排行

C++

超超超生手发一个自编找素数的代码，请大牛过目看看哪里可以优化，求扔砖