素数线性筛

1.素数线性筛核心
　　结论：每一个数都用它的最大素因子将这个合数筛掉。 (27用9筛 15用5筛)
　　理解：合数一定有因子，既然是几个数，就一定有最大的一个。最大因子是唯一的，所以合数只会被它自己唯一的最大因子筛掉一次。

2.如何通过一个数筛去以该数为最大因子的合数
　　结论1:设a是b的最大因子，则b必然等于a乘以一个比a小的素数。(注：对于任意a，b不唯一，比如以15为最大因子的有30和45）
　　理解1：首先，这个数要比a小，若是比a大的数,则最大因子就是不是a了
　　　　　其次，这个数必须是素数，若其为合数，设其为c(b = a * c),因为由于c是合数，那么c又可以分解为若干素数相乘，c=c1*c2*c3...*an，那么c1*a也是b的因子，因而最大因子不是a了。

　　那么,比a小地素数还是有很多，是否需要一个一个去乘呢？答案否定的。

　　结论2：设b=a*c,其中c是素数且c小于等于a的最小素因子，那么b的最大因数就是a。(乘上的数要小于等于a的最小素因数)
　　理解2：设a可以表示为素数成绩，即a=a1*a2*a3*...*1，其中a1为最小素因子(若a本身为素数则a1=a),
　　　　　设另一素数为c,得到的合数b=a*c,假设c大于a的最小素因子a1,那么b=a1*a2*a3...*an*c，由于c大于a1,那么 c*a2*a3*...*an 大于 a1*a2*a3*...*an（即a），那么b的最大素数就不是a了。

　　example：

　　　　假设a为9，那么a的最小素因子为3,小于等于3的素数有2,3，因此以9为最大素因子的合数有 9*2=18, 9*3=27

　　　　假设a为15，那么a的最小素因子为3,小于等于3的素数有2,3,因此以15为最大素因子的合数有 15*2=30, 15*3=45

　　　　假设a为21,那么a的最小素因子为3,小于等于3的素数有2,3,因此用21可以筛去21*2=42, 21*3=63(虽然63=9*7,但63是用21筛去的而不是9,因为9不是63的最大因子而21才是)

3.结论
　　最后我们就可以得出结论：对于每一个数a，乘上小于等于a的最小素因数的素数，就得到以a为最大因数的合数。设有一个数n，只要将所有以比n小的数为最大因数的合数筛去，那么比n小的数里剩下的就只有素数了。

/* 素数线性筛 */
#include <cstdio>
#include <cstring>

const int maxn = 1000;
bool flag[maxn+1];
int prime[maxn + 1];
int priNum;

int main()
{
    priNum = 0; //初始化为0个素数
    memset(flag, 1, sizeof flag); //初始全部标记为素数

    for (int i = 2; i <= maxn; ++i){
        //筛去所有最大因素是i的合数(i*一个素数(该素数不大于i的小素因子的))
        if (flag[i]){
            prime[priNum++] = i; //i是素数记录下来
        }
        for (int j = 0; j < priNum && prime[j] * i <= maxn; ++j){
            //筛去合数
            flag[i*prime[j]] = 0;
            if (i%prime[j] == 0){
                break; //遇到最小素因子，结束
            }
        }
    }
    int kase = 0;
    for (int i = 2; i < maxn; ++i){
        if (flag[i]){
            printf("%d ", i);
            ++kase;
            if (kase % 5 == 0){
                printf("
");
            }
        }
    }

    for (int i = 0; i < priNum; ++i){
        printf("%d ", prime[i]);
        if ((i + 1) % 5 == 0){
            printf("
");
        }
    }


    return 0;
}

View Code