[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)的时间内完成。

加入对话

1条评论

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注