[UVA11408 Count DePrimes]【线性筛】【例题】

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2403

一个数认定为DePrimes当且仅当该数的所有素因子之和为素数。

比如说n=p1^k1 * p2^k2 * p3^k3 那么就要求p1+p2+p3为素数。

然后给出询问a,b，问[a,b]内有多少个这个数。2<=a,b<=5000000

当然这个题目本身暴力O(n lg n)的筛预处理，顺便算出因子和就可以过。

然后记得上次看到JZP神犇blog上的有提到线性筛( O(n) )，那么考虑用到这里。

这个线性筛的基本思想是让每个数字只被它的最小素因子筛到。

下面利用本题代码写个小介绍以防忘记。

void init(){

    int i,j;

    memset(low,0,sizeof(low));    //low[i]里存的是i的最小素因子，特别地，若i是素数，那么low[i]=0

    memset(sum,0,sizeof(sum));    //储存i的素因子和

    low[0]=low[1]=1;

    for (i=2;i<=5000000;i++){

        if (!low[i]) {pl[cnt++]=i; sum[i]=i;}  //i为素数，那么加入素数表，并令它的素因子和为i

        for (j=0;j

/*

这里(!low[i] || pl[j]<=low[i])就是最精髓的地方

这样保证了每次筛的新数pl[j]*i，其最小素因子是pl[j]，

所以假如x不是素数，令low为x的最小素因子，则x只能以x/low * low这种形式被筛到

*/

            low*i]=pl[j];

            sum*i]=sum[i];

            if ((low[i] && pl[j]!=low[i]) || (!low[i] && i!=pl[j])) sum*i]+=pl[j];

        }

    }

    ret[0]=ret[1]=0;

    for (i=2;i<=5000000;i++) ret[i]=ret[i-1]+(!low[sum[i]]);

}

 

int main(){

    init();

    int a,b;

    while (1){

        scanf("%d",&a);

        if (a==0) break;

        scanf("%d",&b);

        printf("%dn",ret[b]-ret[a-1]);

    }

}

有了low这个数组，分解素因子也将能在O(lg n)的时间内完成。