学步园

求1-MAX之间的素数，以及它们的个数，大家都知道，在偶数中，只有2是素数，所以，我们可以认为偶数都不是素数，直接掠过，最后再把2添加进去
这样，我们可以只记录奇数的状态，p[n]，就表示2*n+1是不是素数
=========================================
表示域：
表示元素：n
=====================||===================
实际域：
实际代表的数字：r=2*n+1
筛选从r的平方开始，也就是
r*r=(2*n+1)*(2*n+1)=4*n^2+4*n+1=2*【2*n*(n+1)】+1
转换成表示域就是
=====================||====================
表示域：
2*n*(n+1)就可以表示r*r
=====================||====================
实际域：
现在知道了内层从r*r开始，每次加多少呢？如果加r,也就是2*n+1,那么得到的是
r*(r+1)=4*n^2+6*n+2,很明显，这是个偶数，我们的目的是把偶数全部当合数算
所以，应该找下一个奇数，又是r的倍数，那么很明显，下一个就是
r*(r+2)=4n^2+8n+3
=====================||====================
表示域：
4n^2+8n+3=2[2n^2+4n+1]+1
所以表示域就是
2n^2+4n+1=2n^2+2n+(2n+1)
所以说，表示域每次增加为2n+1
===========================================

下面是代码：

#define MAX 10000001
int p[MAX];
int prime[MAX];
int primenum;
int creatprime2(int lim){//传说中的2倍压缩筛选素数
    int sievelimit = ( sqrt(lim * 1.0) - 1 ) / 2;//只需筛到一半
    int maxindex = ( lim - 1 ) / 2;
    int n,t,k;
    for(n = 1; n <= sievelimit; n++){
        if(p[n] == 0){
            t = 2*n + 1;//每次表示域增加2n+1
            for(k = 2*n*(n+1); k <= maxindex; k += t)//从2n(n+1)开始
                p[k] = 1;
        }
    }
    prime[0] = 2;
    primenum = 1;
    for(n = 1; n <= maxindex ;n++){
        if(p[n]==0)
            prime[primenum++] = 2*n+1;//p[n]==0表示的是2*n+1是素数
    }
    return primenum;
}