根据题主算法以及我后来改进的算法，举个很简单的数：45是个奇数，在打表质数3的合数时，当j从3循环到15时，会将45标注为0。当对质数5的合数打表时，j从5循环到9时，45会再次被打表置0。这种对已知状态的数重复赋值的操作也会影响操作速度的，当很多这种类型的合数被重复打表置0，速度影响就明显了，因此，在以字节为状态表的欧拉筛算法里，可以用一句if(a[i*j])a[i*j]=0来减少赋值（判断只需要从内存读取数据，而赋值既要读也要写，在cpu层面对内存写操作的时钟数多于读操作的时钟数）次数达到提高运行速度。但这种方法在位筛法中不合适，因为定位某一个合数需要好几次乘、除、取余运算，大大降低了定位效率，所以位操作不适合欧拉筛。
顺便说一句：欧拉筛就是我提供的效果图中普通筛和素数表求素数表法的结合，因此欧拉筛需要两个表，在对大范围的素数建表时速度提升明显。

这样快点不？
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
main()
{
    int n,count=0;
    unsigned char *array;
    scanf("%d",&n);
    time_t start=clock(),end;
    array=(unsigned char *)malloc(sizeof(unsigned char)*(int)((n/2+0.5)*1.0/8+0.9));
    for(int i=0;i<(int)((n/2+0.5)*1.0/8+0.9);i++)array[i]=0xff;
    for(int i=3;i*i<=n;i+=2)
        for(int j=i*i;j<=n;j+=2*i)
         {
             array[j/16]&=~(1<<((j-1)/2)%8);
         }
    for(int i=1;i<=n;i+=2)
        if(array[i/16]&(1<<((i-1)/2)%8))
        count++;
        end=clock();
    printf("%d time:%d",count,end-start);
}

[此贴子已经被作者于2017-4-9 13:17编辑过]

在ideone上编译了一下。

从ideone上来看，比我的要快些。

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

经比对，在我电脑上比题主的快300毫秒，没我修改题主代码后快（我修改题主代码后是3000毫秒左右），比我的代码慢，对比图如下：

这是我在15楼修改的代码运行结果，2875毫秒，比我的代码慢不到1秒：

你15楼的代码我竟然忽略了一个比较重要的一点，内嵌的for中将乘法改成加法。
啊啊啊啊啊啊。

是的，做加减肯定比做乘除、取余运算效率高。

没道理呀，我电脑上运行为什么比15楼快一秒？
发现还是25楼最快。

[此贴子已经被作者于2017-4-9 12:24编辑过]

嗯，看来这和编译器优化方式或cpu架构有关，我的是早期的2.4G酷睿2四核芯片，用vs2010编译。
25楼的确最快，在我电脑上是1813毫秒，比我的快，要学习下。、
25楼快在内循环的步进上，他是for( j = i*i; j<=n;j+=i*2)，他是从i*i开始步进，步进幅度是i*2，也就是说，随着找到的质数越大，步进的幅度越大，避开了重复给合数打表的过程，高！

13:17更：
学习了25楼算法后，立马用到我的代码里，耗时缩小到1734毫秒。

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

编程时算法很重要，是要努力学习的，虽然很难学，但必须去学，
程序的优化，从代码效率或者cpu效率着手，虽然很重要，效果有时也很明显，但这些在算法优化面前就显得太弱小了，比如这个求素数个数问题，试除法与筛法比较无论如何优化也难以望其相背，即使时筛法，在更好的算法面前速度也是太慢了，完全不在一个数量级上。以下给出一段代码，应用两种不同的算法，可以看到两种算法在速度上有着巨大的差别，运行好的算法，可以有飞一样的感觉，来感受一下吧。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <string.h>
#include<math.h>
#include <time.h>

#define LINT long long

int main01(int n )
{
     unsigned char *BITArray;
     long maxsize;
     long i, j;
int sqn,k;


if(n==2)return  1;
if(n<2)return 0;
k=1;

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);
 
     return k;
}
int main( )
{
int m,n;
int main01( int);
int main02( int);
LINT primesum(LINT N);
long t;
printf("main01:\n");


t=clock();
n=300000000;
m=main01(n);
 printf("n= %d time:%ld   sum:%d\n",n,clock()-t,m);
printf("main02:\n");

t=clock();
n=300000000;
m=main02( n);
 printf("n= %d time:%ld   sum:%d\n",n,clock()-t,m);

printf("primesum:\n");


t=clock();
n=300000000;
m=primesum(n) ;
 printf("n= %d time:%ld   sum:%d\n",n,clock()-t,m);

t=clock();
n=2000000000;
m=primesum(n) ;
 printf("n= %d time:%ld   sum:%d\n",n,clock()-t,m);
return 0;
}

int main02( int n)
{
     unsigned int*BITArray;
     int maxsize,i,j,k;
int temp,sqn;
   
if(n==2)return  1;
if(n<2)return 0;
k=1;

     maxsize =n/ 64+((n%64)!=0);
     BITArray = ( unsigned int* )malloc( maxsize * sizeof( unsigned int) );
memset(BITArray,0,maxsize*sizeof(unsigned int));
     assert( NULL != BITArray );
sqn=(int)(sqrt(n)+0.5);
   
     for( i = 3;i<=sqn;i+=2)
      
          {
      temp=(i-3)/2;
         if( (BITArray[temp/32] & ( 1u << (temp%32)))==0 )
             {
                 ++k;
      
         for( j=i*i;j<=n;j+=i*2)
{
temp=(j-3)/2;
                        BITArray[temp/32]|=(1u<<(temp%32));
}
}
}
  for(;i<=n; i+=2)
{
      temp=(i-3)/2;
         if( (BITArray[temp/32] & ( 1u << (temp%32)))==0 )
            
                 ++k;
 }
free(BITArray);
 
     return k;
}
inline LINT V2IDX(LINT v, LINT N, LINT Ndr, LINT nv) {
    return v >= Ndr ? (N/v - 1) : (nv - v);
}

LINT primesum(LINT N) {
    LINT *S;
    LINT *V;
LINT sum;
    LINT r = (LINT)sqrt(N);
    LINT Ndr = N/r;

    assert(r*r <= N and (r+1)*(r+1) > N);

    LINT nv = r + Ndr - 1;

    V = new LINT[nv];
    S = new LINT[nv];

    for (LINT i=0; i<r; i++) {
        V[i] = N/(i+1);
    }
    for (LINT i=r; i<nv; i++) {
        V[i] = V[i-1] - 1;
    }

    for (LINT i=0; i<nv; i++) {
        S[i] = V[i]- 1;
    }

    for (LINT p=2; p<=r; p++) {
        if (S[nv-p] > S[nv-p+1]) {
            LINT sp = S[nv-p+1];
            LINT p2 = p*p;
            for (LINT i=0; i<nv; i++) {
                if (V[i] >= p2) {
                    S[i] -= (S[V2IDX(V[i]/p, N, Ndr, nv)] - sp);
                } else {
                    break;
         

}
            }
        }
    }
sum=S[0];
delete(S);
delete(V);
    return sum;
}

下面是以上代码在某在线编程网站运行的结果。
main01:
n= 300000000 time:1640964   sum:16252325
main02:
n= 300000000 time:1532777   sum:16252325
primesum:
n= 300000000 time:11829   sum:16252325
n= 2000000000 time:45016   sum:98222287