这道题貌似在很多地方都有出现，就我所记得的就有《C和指针》、《算法》。
效果还不错。
1亿以内的质数，不到1分钟得出结果，只是存储结果的文本文档有60.6M，让人完全没有打开的欲望。

额外吐槽一句：《算法》中的代码风格简直糟糕透顶，对比起来《数据结构与算法分析》的代码风格简直业界良心。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>

int
main( void )
{
     unsigned char *BITArray;
     long maxsize;
     long i, j, k;

     scanf( "%ld", &maxsize );    
     maxsize = maxsize / CHAR_BIT;
     BITArray = ( unsigned char * )malloc( maxsize * sizeof( unsigned char ) );
     assert( NULL != BITArray );

     for( i = 0; maxsize > i; ++i )
         BITArray[ i ] |= 0xAA;
     BITArray[ 0 ] = 0xAC;

     for( i = 3; maxsize * CHAR_BIT > i * i; ++i )
         if( BITArray[ i / CHAR_BIT ] & ( 1 << i % CHAR_BIT ) )
             for( j = 2; maxsize * CHAR_BIT > ( k = j * i ); ++j )
                        BITArray[ k / CHAR_BIT ] &= ~( 1 << ( k % CHAR_BIT ) );

     for( i = 2,j = 0; maxsize * CHAR_BIT > i; ++i )
         if( BITArray[ i / CHAR_BIT ] & ( 1 << i % CHAR_BIT ) )
             /*printf("%10ld%c",i, (j + 1) % 8 ? ' ' : '\n'), */++j;

     printf( "\n%ld\n", j );

     return 0;

}

[此贴子已经被作者于2017-4-7 01:36编辑过]

用各种方法求大素数表，我还是认真写过的。对你代码稍作修改，和我写过的代码做了对比，首先你的位法比我的位法用时多近2倍（我的用时不到2秒，你的3。6秒），其次你的1亿内素数总数结果和我的不同，我的代码是进过传统求素数法验证的，所以你的结果应该是错的，对比图如下（图中用时均为毫秒）：

为获得1亿内素数总数，修改你的代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#define BIT ( sizeof( unsigned char ) * 8 )

int
main( void )
{
    unsigned char *BitArray;
    long maxsize;
    long i, j,t;

    scanf( "%ld", &maxsize );
    t=clock();
    maxsize = maxsize / BIT;
    BitArray = ( unsigned char * )malloc( maxsize * sizeof( unsigned char ) );
    assert( NULL != BitArray );

    for( i = 0; maxsize > i; ++i )
        BitArray[ i ] |= 0xFF;

    for( i = 2; maxsize * BIT > i; ++i )
        if( BitArray[ i / BIT ] & ( 1 << i % BIT ) )
            for( j = i; maxsize * BIT > j * i; ++j )
                    BitArray[ j * i / BIT ] &= ~(1 << ( j * i % BIT ));

    for( i = 2,j = 0; maxsize * BIT > i; ++i )
        if( BitArray[ i / BIT ] & ( 1 << i % BIT ) )++j;;
            //printf("%10ld%c",i, (j + 1) % 8 ? ' ' : '\n'), ++j;
    printf("time:%d   sum:%d\n",clock()-t,j);

    return 0;

}

想不到问题出在哪儿。

先丢在这儿，等哪天想起了再来弄。

[此贴子已经被作者于2017-4-6 09:30编辑过]

看懂了少少~大概就是一个char共8个数位可以记录8个数状态这样节省空间吧~

是的。程序的其他部分就是筛选法了。

但是程序貌似还有问题，完全想不到在哪儿，先丢在这儿，等哪天有时间了再来慢慢弄。

用位运算代替+-*/...运算

大素数有什么好方法？

筛选法了。速度飞快。

对于位运算符我掌握的很烂。

[此贴子已经被作者于2017-4-6 09:32编辑过]

不好意思，没说清楚。
是大素数，不只是大量素数，大素数要能突破数值类型的限制。

对啦，帮我把帖子下沉一下了。程序有错，免得祸害别人。