传统的写法.

#include <stdio.h>
#include <math.h>
#define  cnt  50000000
int main(void)
{
    int i;
    int j;
    int a[cnt];               

    for (i = 1; i <= cnt; i++) 
        a[i] = i;

    for (i = 2; i < sqrt(cnt); i++)     
        for (j = i + 1; j <= cnt; j++)  
        {
            if (a[i] != 0 && a[j] != 0) 
                if (a[j] % a[i] == 0)
                    a[j] = 0;           
        }
/*
    int n = 0;    

    for (i = 2; i <= cnt; i++)    
    {
        if (a[i] != 0)
        {
            printf("%-5d", a[i]); 
            n++;
        }
        if (n == 10)
        {
            printf("\n");         
            n = 0;
        }
    }
    printf("\n");
*/
    return 0;
}

我的写法

#include <stdio.h>
#define   cnt  50000000
int uDel(int arry[] , int n) {
    int  i  , val;
    for (i = 0 ; i  < n ; i++ ) {
         if (arry[i] == 0)
             continue ;
         else {
                val = arry[i] ;
               return val ;
         }
    }
}

int main(void) {

    int  arry[cnt] ={0,0};
    int  i , j ;
    for (j = 2 ; j < cnt ; j++ )
         arry[j] = j ;
         
    for (i = uDel(arry,cnt) ; i * i <= cnt ; i = uDel(arry , cnt)) {
         // printf("%d " , i) ;
          for (j = 1 ; j * i < cnt ; j++) 
               arry[j * i] = 0 ;
          
    }
    /* for ( i = 0 ; i < cnt ; i++) 
        if (arry[i] != 0 )
         printf("%d " , arry[i]) ;  
    */
  
  return 0 ;
}

注意上面 cnt 50000000 是我在unix-center上的服务器测试用的,普通的pc的内存早就超出了限制.在你机器上适当的改小.
另外,把输出语句注释掉是应为printf太耗时,这里单纯的比较算法.我在unix-center上的一台freebsd6.2系统上分别运行(数量级50000000)了两个程序,我的在2秒内完成,而传统的写法我等了2分多钟.

收到的鲜花

• 广陵绝唱 于 2008-12-10 18:29 送鲜花  49朵   附言：原创内容

敢问这位大大,
"高效"指的是算法吗?
是不是什么O(N)这个东西????????
至于这个程序是干什么的我还要到机子上运行下才知道

哈哈，是不是有点曲高而和者寡的感觉？

另外，悄悄告诉你，你的键盘的＂Ｅ＂键要修理一下了

闲着没事干，给你改了下：

#include <stdio.h>
#include <math.h>
#define   N  50000000

int main(void) {

    static int  array[N+1] ={0,1,2};
    int  i , j ,k, mid;

    for (j = 3 ; j < N ; j++ )
        if(j&1)
            array[j] = j ;

    mid = (int)sqrt((double)N);
    for (i = 3; i <= mid; i++) {
        if(!array[i])
            continue;
        k = N / i;
        for (j = 3 ; j < k ; j++)
            array[j * i] = 0 ;         
    }
    
    return 0 ;
}

发现刚才写的比较笨，优化一下：

#include <stdio.h>
#include <math.h>
#define   N  50000000

int main(void) {

    static int  array[N+1] ={0,1,2};
    int  i , j ,k, mid;

    for (j = 3 ; j <= N ; j+=2)
        array[j] = j ;

    mid = (int)sqrt((double)N);
    for (i = 3; i <= mid; ) {        
        k = N / i;
        for (j = 3 ; j < k ; j++)
            array[j * i] = 0 ;  
        while(!array[++i]&&i<=mid)
            NULL;
    }
    
    return 0 ;
}

[[it] 本帖最后由 rootkit 于 2008-12-10 23:38 编辑 [/it]]

我上看下看，左看右看，原来是个筛法求素数。。。。

就是不知道Erastothens是啥意思。。。

我目前只会传统的筛法

多谢各位捧场.to 老K,你给我买个新的键盘如何

多谢各位捧场.to 老K,你给我买个新的键盘如何

许久不见vxworks了