不过你说的问题，也的确是个问题。

原来莫名其妙的崩溃还就是你说的那个BUG。奇怪的是，计算的数字少一点就不会崩溃，大于5W就会崩溃。

奇奇怪怪的，在刚开始存在计算问题的时候，这个BUG还不存在，我一修复，这个BUG就出现了。

找到的原因是：
i到100000000循环，显然当i=99999997（实际上不需要到这个数）时是质数，j=i,筛掉的合数为99999997*99999997,数据溢出出错。从2循环时3*100000000/2在数据未溢出时就退出循环了，所以不出错。
还有一种避免的方法是i到sqr(100000000)循环，也不会导致数据溢出，能得到正确答案，如下：

...
     for( i = 2; maxsize * CHAR_BIT >= i*i; ++i )  //从2到sqr(100000000)循环，也能得到正确答案
         if( BITArray[ i / CHAR_BIT ] & ( 1 << i % CHAR_BIT ) )
             for( j = i; maxsize * CHAR_BIT > j * i; ++j )
                        BITArray[ j * i / CHAR_BIT ] &= ~( 1 << ( j * i % CHAR_BIT ) );
...

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

嗯嗯。谢啦。

我仔细想想。

当时发这贴的时候，没想到存在严重BUG，所以没写问题点数。现在我在外面重新开了个结分的帖子，你有时间的话回一下吧。

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

看了几段代码，觉得有几个问题，
maxsize = maxsize / CHAR_BIT;
整除余数被舍去，如果 小于maxsize 的附近有质数就会遗漏，改为 maxsize = maxsize / CHAR_BIT+(maxsize %CHAR_BIT!=0);
for( i = 0; maxsize > i; ++i );
此句等效为
for( i = 0; i<=maxsize ; ++i )
当有maxsize 个空间时，越界难免，低级错误。
for( i = 3; maxsize * CHAR_BIT > i * i; ++i )
         if( BITArray[ i / CHAR_BIT ] & ( 1 << i % CHAR_BIT ) )
数据与标记数组对应关系有问题。

附上修改后的代码供参考。


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <string.h>
#include<math.h>
#include <time.h>
int main( )
{
     unsigned char *BITArray;
     long maxsize;
     long i, j,n=100000000;
int t,sqn,k=1;
     //scanf( "%ld", &n);
t=clock();
maxsize = n / CHAR_BIT+(n%CHAR_BIT!=0);
   
     BITArray = ( unsigned char * )malloc( maxsize * sizeof( unsigned char ) );
     assert( NULL != BITArray );

     for( i = 0;i< maxsize; ++i )
         BITArray[ i ] = 0xff;
   
sqn=(int)(sqrt(n)+0.001);
     for( i = 3; i<=sqn; i+=2)
      if( BITArray[ (i -3)/ CHAR_BIT ] & ( 1 << (i -3)% CHAR_BIT ) )
{
++k;
             for( j = i*i; j<=n;j+=i*2)
                        BITArray[( j -3)/ CHAR_BIT ] &= ~( 1 << (( j -3) % CHAR_BIT ) );
}

     for( ;i<=n ;i+=2)
         if( BITArray[ (i -3)/ CHAR_BIT ] & ( 1 <<( i-3) % CHAR_BIT ) )
        ++k;
free(BITArray);
    printf("time:%d   sum:%d\n",clock()-t,k);

     return 0;
}

又看了一遍，这回看懂了。大致说一下，
楼主判断一个范围内的数是否为质数的方法是：先把范围内的质数筛选，筛选方法为这个数除以8（姑且不考虑大于8的情形），得到的余数为1,3,5,7的数才
有可能是素数。于是楼主把除array[0]外的所有数组元素初始化为0xaa（即 1010 1010,1左移1,3,5,7位）。在0-7中只有2,3,5,7为质数，所以array[0]初始化为0xac。
然后是从3－sqrt(maxsize)内筛选素数。这里i的增量，建议改为2,可以节省一半的判断。再然后就是去合数，把原素数范围内数乘以2-maxsize/i范围内数得到的合数从原
表中去掉。这里是否要考虑重复操作的问题，比如11*13和13*11结果一样，这样就多余操作一次。最后就是累加质数个数，不多说。

[此贴子已经被作者于2017-4-8 21:10编辑过]

i的增量已经接纳了xzl版主的建议改成2了，不过修改后的代码没有放上来。

[此贴子已经被作者于2017-4-8 21:31编辑过]

这样理解？好像不完全正确。
除以8，是因为内存申请是以字节为单位的，而一个字节为8位，不可能有大于8位的情况存在（题主不应该以char的长度为标准），除以8的主要目的是未了减少建立筛表占用的空间。在建立大素数表时，也就是各种筛法速度最快（位表筛法和数据范围小的都不适用欧拉筛），但筛法需要一个大数范围内的表，如建立2^32内的素数表，你首先得有一个2^32的表，传统筛法就需要申请4G的内存，这怎么可能申请得到？所以位表筛法应运而生，用字节中的每位的状态表示该数是否为素数（一般编程者会规定1表示为素数，0表示为合数），这样你只需要申请4G/8=0.54G的内存了。实际上，如果你觉得申请540M内存都嫌多，由于偶数不可能为素数，因此偶数是不需要打表的，你还可以通过算法只申请540/2=270M内存的，我的欧拉筛法打表就去掉了偶数的表。
至于重复在合数位上设置状态的情况确实存在，对于用普通字节欧拉筛算法里可通过一个判断语句跳过，这样可以提高些速度（不同机器速度提高的不同），但在位表中反而会降低速度，主要是位表筛法位计算牺牲了速度。
另jklqwe111说的题主代码问题确实存在，我的位表筛法在申请时不管除8是否除尽，我都增加了一个字节。
以下是我的代码在求30000000以内素数表在本机上所用的时间运行效果图：

这句怎么理解？~有点不太明白~

一下是我在网上搜到的欧拉筛法代码~对比下和位运算的有什么不同~~~

#include<stdio.h>

#define MAX 100
char IsPrime[MAX+1]={0};
int prim[MAX+1]={0};

int main()
{
    int i=0;
    int j=0;
    int num=0;

    for (i=2;i<=MAX;++i)
    {
        if (!IsPrime[i])
            prim[num++]=i;

        for (j=0;j<num&&i*prim[j]<=MAX;++j)
        {
            IsPrime[i*prim[j]]=1;

            if (i%prim[j]==0)
                break;
        }
    }

    for (i=0;i<num;++i)
        printf("%-4d",prim[i]);

    puts("");

    return 0;
}