计算素数
kflnig
    在《看雪精华7》中看到一篇关于大家都在算素数的文章，很好玩，于是乎，我自己也来试试，看看能否打破记录。我本是只菜鸟，复杂一点点的算法，就不会。好了，我们还是来看看吧。在写这篇文章前，我还不知道怎么使用GetTickCount（）这个api呢。
    我就直接贴个程序了。那篇文章里最后一个家伙恐怖的说：“计算到260万，340ms。”不知道他的CPU是什么，我的是32位菜羊2.66GHZ。很老的一个型号了。好久好久没有编程了，甚至快连编一个求素数的都快不会了。
    首先把menglv的VB程序写的东西C++化，假设他们的机器和我的相同。发现VB和C++的执行速度要差上好几倍。2――10000，他在vb里203毫秒。我这边有时是16ms有时是0ms。把他的数据提高到2??一百万。那么时间是1.9s。这绝对是不行的。
    我的算法运用了一个定理，以前看《离散数学》的时候看来的，学以致用嘛，大概就是说，若一个数n不能被sqrt（n）之内的素数整除，那么这个数就是素数。写好之后计算了一下时间，看来我只能来当反面教材了。我的代码如果写错了，大家告诉我。
#include <iostream.h>
#include <windows.h>
#include <math.h>
void main()
{
long t1,t2,n1=12,n2,n3,ss[200000];
bool fg=false;
        t1=GetTickCount();
        ss[0]=2;        ss[1]=3;        ss[2]=5;        ss[3]=7;        ss[4]=11;        n3=4;
while (n1<=1000000)
        {
        for (n2=0;n2<=n3;n2++)
        {
                if (sqrt(n1)<ss[n2]) break;
                if (n1 % ss[n2]==0)  {fg=false;break;}
                else fg=true;
        }
        if (fg==true) {n3++;ss[n3]=n1;fg=false;}
        n1++;
        }
t2=GetTickCount();
cout<<t2-t1;
}
约600ms大一点。天啊！怎么可以，其实只要改一个语句就可以把时间缩短到275ms左右。一半时间啊！
if (sqrt(n1)<ss[n2]) break;――>if (n1<ss[n2]*ss[n2]) break;
    惊奇吧！只要改这么一个语句就够了哟！以后大家要注意了可以×解决的绝对不开方。
可是那个最嚣张的家伙说“计算到1001989，使用时间120ms。”如果它的机器不是大型机那么就说明，我的代码还欠优化。显然，if (n1<ss[n2]*ss[n2]) break;这句语句还是不够理想。可是这句实在是无法优化。我们必须得等价的实现一种方法。
这里的判断太要人命了。我们要设法减少。可是这句话又关系着下面一句的实现。这句话的繁，使得下面一句做了最少的运算。于是乎采取了一个折衷的算法。就是分两步计算。先算1000以内的素数，然后求得1000×1000内的素数。
#include <iostream.h>
#include <windows.h>
#include <math.h>
void main()
{
long t1,t2,n1=12,n2,n3,num,ss[200000];
bool fg=false;
        t1=GetTickCount();
        ss[0]=2;        ss[1]=3;        ss[2]=5;        ss[3]=7;        ss[4]=11;        n3=4;
while (n1<=1000)
        {
        for (n2=0;n2<=n3;n2++)
        {
                if (n1<ss[n2]*ss[n2]) break;
                if (n1 % ss[n2]==0)  {fg=false;break;}
                else fg=true;
        }
        if (fg==true) {n3++;ss[n3]=n1;fg=false;}
        n1++;
        }
num=n3;
while (n1<1000000)
{
        for (n2=0;n2<num;n2++)
        {
                if (n1 % ss[n2]==0)  {fg=false;break;}
                else {fg=true;}
        }
        if (fg==true) {n3++;ss[n3]=n1;fg=false;}
        n1++;
}
t2=GetTickCount();
cout<<t2-t1;
}
不优化则已，一优化时间哗的涨到350ms。印证了我“可是这句话又关系着下面一句的实现。这句话的繁，使得下面一句做了最少的运算。”这句话。
怎么办？
再想办法。不考虑算法，突然想到，c语言中可以有寄存器变量。由于外层循环很大我们可以定义一个寄存器变量。我们把n1定义成register n1;这个模样。还是没有多大变化。只是，在多次运行中出现了最短时间为265ms了。
再稍微改一下。
n1=12;n3=4;num=4;
while (n1<=1000000)
        {
        if (n1>ss[num]*ss[num]) num++;//这里变了
        for (n2=0;n2<=num;n2++)
        {
              if (n1 % ss[n2]==0)  {fg=false;break;}
                else fg=true;
        }
        if (fg==true) {n3++;ss[n3]=n1;fg=false;}
        n1++;
        }
稍微又比刚才好了一点点。缩短了10ms。
我把我自己的方法的最好只能是这样了。好了，上面的就是我的所得了。可惜我实在无法再进一步优化了。点击Vc中的那个！执行和直接在CMD中执行会差上10ms左右。
kflnig极限：265ms。可是据说GetTickCount()的精度不高。可能还要稍微高一点。我到2百万数据已经和那位帅哥没得比了。所以不说了。
本来还想装一下酷，来个费马小定理。想想，作罢了。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课