# M.J的blog

algorithm,ACM-ICPC

## 【数论内容】线性筛素数，线性筛欧拉函数，求前N个数的约数个数

` 1 #include<stdio.h> 2 #include<string.h> 3 #define M 10000000 4 int prime[M/3]; 5 bool flag[M]; 6 void get_prime() 7 { 8     int i,j,k; 9     memset(flag,false,sizeof(flag));10     k=0;11     for(i=2;i<M;i++){12         if(!flag[i])                            13         prime[k++]=i;14         for(j=0;j<k&&i*prime[j]<M;j++){15             flag[i*prime[j]]=true;            16             if(i%prime[j]==0)             17                 break;18         }19     }20 }21 int main()22 {}`

-----------------------------------------------------------------------我是低调的分割线------------------------------------------------------------------------------------------

//(1) 若(N%a==0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a;
//(2) 若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);

(1) phi[p]=p-1;  (p为素数);
(2)若N=p^n(p为素数)，则 phi[N]=(p-1)*p^(n-1);

` 1 #include<stdio.h> 2 #include<string.h> 3 #define M 10000000 4 int prime[M/3],phi[M]; 5 bool flag[M]; 6 void get_prime() 7 { 8     int i,j,k; 9     memset(flag,false,sizeof(flag));10     k=0;11     for(i=2;i<M;i++){12         if(!flag[i]){                            13             prime[k++]=i;14             phi[i]=i-1;15         }16         for(j=0;j<k&&i*prime[j]<M;j++){17             flag[i*prime[j]]=true;            18             if(i%prime[j]==0){19                 phi[i*prime[j]]=phi[i]*prime[j];20                 break;21             }22             else23                 phi[i*prime[j]]=phi[i]*(prime[j]-1);24         }25     }26 }27 int main()28 {}`

-----------------------------------------------------------------------我是低调的分割线-----------------------------------------------------------------------------------------

div_num[N]=(p1+1)*(p2+1)*(p3+1)* ... *(pn+1);

对于div_num：

(1)如果i|prime[j] 那么 div_num[i*prime[j]]=div_sum[i]/(e[i]+1)*(e[i]+2)                  //最小素因子次数加1
(2)否则 div_num[i*prime[j]]=div_num[i]*div_num[prime[j]]                                     //满足积性函数条件

对于e：

(1)如果i|pr[j]  e[i*pr[j]]=e[i]+1; //最小素因子次数加1
(2)否则 e[i*pr[j]]=1;              //pr[j]为1次

` 1 #include<stdio.h> 2 #include<string.h> 3 #define M 10000000 4 int prime[M/3],e[M/3],div_num[M];           // e[i]表示第i个素数因子的个数 5 bool flag[M]; 6 void get_prime() 7 { 8     int i,j,k; 9     memset(flag,false,sizeof(flag));10     k=0;11     for(i=2;i<M;i++){12         if(!flag[i]){                            13             prime[k++]=i;14             e[i]=1;15             div_num[i]=2;                       //素数的约数个数为216         }17         for(j=0;j<k&&i*prime[j]<M;j++){18             flag[i*prime[j]]=true;            19             if(i%prime[j]==0){20                 div_num[i*prime[j]]=div_num[i]/(e[i]+1)*(e[i]+2);21                 e[i*prime[j]]=e[i]+1;22                 break;23             }24             else{25                 div_num[i*prime[j]]=div_num[i]*div_num[prime[j]];26                 e[i]=1;27             }28         }29     }30 }31 int main()32 {}33 34 35 `

posted on 2010-04-28 16:56 M.J 阅读(3600) 评论(11)  编辑 收藏 引用

## #re: 【数论内容】线性筛素数，线性筛欧拉函数，求前N个数的约数个数[未登录]  回复更多评论

2010-04-28 17:37 | chaogu

## #re: 【数论内容】线性筛素数，线性筛欧拉函数，求前N个数的约数个数  回复更多评论

2010-04-28 22:50 | M.J

## #re: 【数论内容】线性筛素数，线性筛欧拉函数，求前N个数的约数个数  回复更多评论

1 | 1,1 | 2,1 | 3
2 | 3,
3 | 3

2010-04-29 12:22 | schindlerlee

## #re: 【数论内容】线性筛素数，线性筛欧拉函数，求前N个数的约数个数  回复更多评论

2010-04-29 16:40 | M.J

## #re: 【数论内容】线性筛素数，线性筛欧拉函数，求前N个数的约数个数  回复更多评论

2010-05-03 16:20 | abilitytao

## #re: 【数论内容】线性筛素数，线性筛欧拉函数，求前N个数的约数个数  回复更多评论

2010-05-06 22:59 | M.J

## #re: 【数论内容】线性筛素数，线性筛欧拉函数，求前N个数的约数个数  回复更多评论

2010-07-19 16:13 | dlut_thinkers

## #re: 【数论内容】线性筛素数，线性筛欧拉函数，求前N个数的约数个数  回复更多评论

2: 2
3: 2
4: 3
5: 2
6: 4
7: 2
8: 4
9: 3
10: 4
11: 2
12: 8
13: 2
14: 4
15: 4
16: 5
17: 2
18: 6
19: 2
20: 8
20的约数个数是不是应该是6？
2010-08-08 17:26 | lzbltx

## #re: 【数论内容】线性筛素数，线性筛欧拉函数，求前N个数的约数个数[未登录]  回复更多评论

@lzbltx

2010-08-17 22:01 | M.J

## #re: 【数论内容】线性筛素数，线性筛欧拉函数，求前N个数的约数个数  回复更多评论

Orz下！
2010-12-08 22:57 | syx

## #re: 【数论内容】线性筛素数，线性筛欧拉函数，求前N个数的约数个数回复更多评论

26行写错了。。。应为e[i*prime[j]]=1;
2011-08-25 14:58 | xyz