⊙﹏⊙b汗~~~ 这就是算法的力量呀！！

没有半小时，是得不出结果的，我原先以为会很快的，可是我等了20多分钟都不见结果……

#include<stdio.h>
#define M (2000000+1)
char v[M];
int r[150000];
int p = 0;
int main(void)
{
    int i, j, t;
    for(i=2; i<M; i++)
    {
        if(!v[i])
        {
            r[p++] = i;
            printf("%d ", i);
        }
        for(j=0; j<p; j++)
        {
            if((t=i*r[j]) >= M) break;
            v[t] = 1;
            if(i%r[j] == 0) break;
        }
    }
    puts("");
    return 0;
}

更大数据规模下，此算法比10楼要快许多。复杂度是O(n)，大概算1亿的质数不到10秒（不包括输出时间）。

[ 本帖最后由 卧龙孔明 于 2011-4-11 00:14 编辑 ]

难道是我和孔明的 Sieve ? 绝对滴不可能

这种程序的复杂度感觉不太好估算，不过孔明的会快倒是很明显。

#include<stdio.h>
#include<dos.h>
#include<math.h>
main()
{
    long i,j,k=0;
    int h,m,s;
    struct time t[1];
    gettime(t);
    h=t[0].ti_hour;/*显示开始执行的时间*/
    m=t[0].ti_min;
    s=t[0].ti_sec;
    printf("%d:%d:%d\n",h,m,s);
    for(i=3;i<2000000;i++)
    {
        for(j=2;j<sqrt(i);j++)
        {
            if(i%j==0) break;
        }
        if(j>=i) k++;
    }
    gettime(t);
    h=t[0].ti_hour;
    m=t[0].ti_min;
    s=t[0].ti_sec;
    printf("\n%d:%d:%d\n",h,m,s);/*显示执行完成后的时间*/
    sound(5000);
    delay(100);
    printf("%d",k);
    getch();
}/*改进算法之后，运行时间为2分3秒*/
以前不注意算法的时间复杂度，随意设计。现在通过这题，发现一个好的算法，一个高效的算法能成倍的提高程序的运行速度。

孔明，我有个问题，把数组定义为全局最大长度可以多大？ 定义为一个函数的本地变量最大长度可以多大？

[ 本帖最后由 voidx 于 2011-4-11 12:43 编辑 ]

如果你对他的算法质疑的话，我建议你上机试一下……

哦哦哦哦哦楼主在程序优化啊我就知道n+=2  就不用算偶数了除的时候好像开个方就又能优化一步菜鸟   勿耻

另外啊 ，小生有一不情之请望各位给予重视。每当看到大虾牛逼的算法而望洋兴叹之时，多么希望各位给予引导我相信各位大虾都看过C大学教程，能不能像他们一样在下面给些许解释呢，或者 给些注释也行