大家帮我看看 是不是这样子筛选的  是否有漏洞 或者有待优化的地方

#include <stdio.h>
#define max 300

//使用筛选法列举素数
int main()
{
    int i=2;
    int k,j;
    int t[max]={0};
    for(k=0;k<max;k++) t[k]=i+k;   //为待扫描数据赋初值 自然数序列 从2开始
    i=0;
    k=t[i];  //初始素数
    while(i<max)
    {
        i++;
        for(j=i;j<max;j++) if(t[j]%k==0) t[j]=0;  //凡能够整除者 赋0
        while(t[i]==0) i++;  //搜索下一个素数
        k=t[i];
    }
    for(k=0;k<max;k++)
    {
        if(t[k]!=0) printf("%d ",t[k]);    //不是0者，即素数 打印输出
    }
    printf("\n");
    return 0;
}

用一个bit就可以保存一个数字，因此你可以压缩到 1/sizeof(int)*8
2的倍数参与计算了，你又可以再压缩 1/2

都说用bit保存数字  不知道具体咋弄呢  能给一段示例 研究一下！！

表示没有看懂

比如我这代码代码，第0个bit表示3，第1个bit表示5，第2个bit表示7，……

你用int[300]算到293
我只用int[5]就可以算到317

但代码是我仓促写的（可能有错误），你参考一下

#include <stdio.h>

#define MAX 5

#define COUNT        ( MAX*sizeof(unsigned)*8 )
#define IDX2VAL(i)   ( i*2+3 )
#define TESTBIT(t,i) ( (t[i/(sizeof(t[0])*8)] & 1u<<(i%(sizeof(t[0])*8))) == 0 )
#define INVLBIT(t,i) ( t[i/(sizeof(t[0])*8)] |= 1u<<(i%(sizeof(t[0])*8)) )

int main()
{
    unsigned t[MAX] = { 0 };
    for( size_t i=0; IDX2VAL(i)*2<=IDX2VAL(COUNT-1); ++i )
        if( TESTBIT(t,i) )
            for( size_t j=i+IDX2VAL(i); j<COUNT; j+=IDX2VAL(i) )
                INVLBIT(t,j);

    printf( "%u ", 2 );
    for( size_t i=0; i!=COUNT; ++i )
        if( TESTBIT(t,i) )
            printf( "%u ", IDX2VAL(i) );

    printf("\n");
    return 0;
}

果然有问题，
IDX2VAL(i)*2<=IDX2VAL(COUNT-1)
应当改为
IDX2VAL(i)*3<=IDX2VAL(COUNT-1)
虽然不影响结果

下班了，明天我再仔细检查一下

------------------------------------------

代码没错，但我稍微改一下，以便于理解。

#include <stdio.h>

#define BUFSIZE 300

#define BITCOUNT     ( BUFSIZE*sizeof(unsigned)*8 )
#define IDX2VAL(i)   ( i*2+3 )
#define TESTBIT(t,i) ( (t[i/(sizeof(t[0])*8)] & 1u<<(i%(sizeof(t[0])*8))) == 0 )
#define INVLBIT(t,i) ( t[i/(sizeof(t[0])*8)] |= 1u<<(i%(sizeof(t[0])*8)) )

int main()
{
    unsigned t[BUFSIZE] = { 0 };
    for( size_t i=0; i+IDX2VAL(i)<BITCOUNT; ++i )
        if( TESTBIT(t,i) )
            for( size_t j=i+IDX2VAL(i); j<BITCOUNT; j+=IDX2VAL(i) )
                INVLBIT(t,j);

    printf( "%u ", 2 );
    for( size_t i=0; i!=BITCOUNT; ++i )
        if( TESTBIT(t,i) )
            printf( "%u ", IDX2VAL(i) );

    printf("\n");
    return 0;
}

使用bit的好处是，不但节约了内存，而且因为内存寻址范围小了，使得运行效率更高。遍历一个int的32(64)个bits 要快于 遍历32(64)个int。
而且在数据量更大的情况下，还会涉及到内存页的切换，这个代价更大，所以要尽量减少内存页切换次数。


[ 本帖最后由 rjsp 于 2014-4-3 09:16 编辑 ]

我是嫩手啊....高手都不喜欢在for()后面加上{}吗？上面已经定义了i=2，为何下面又要定义i=0呀？

来学习学习。。

前来学习

楼主刚刚回我贴了，我来学习学习