M.J的blog

algorithm,ACM-ICPC
随笔 - 39, 文章 - 11, 评论 - 20, 引用 - 0
数据加载中……

【数论内容】线性筛素数,线性筛欧拉函数,求前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 {}
 

利用了每个合数必有一个最小素因子,每个合数仅被它的最小素因子筛去正好一次,所以是线性时间。
代码中体现在: if(i%prime[j]==0) break;
-----------------------------------------------------------------------我是低调的分割线------------------------------------------------------------------------------------------
然后可以利用这种线性筛法求欧拉函数,需要用到以下几个性质:
//(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); 
其中a是N的质因数。
关于欧拉函数还有以下性质:
(1) phi[p]=p-1;  (p为素数);
(2)若N=p^n(p为素数),则 phi[N]=(p-1)*p^(n-1);
关于欧拉函数,Wiki有很详细的介绍。

 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             else
23                 phi[i*prime[j]]=phi[i]*(prime[j]-1);
24         }
25     }
26 }
27 int main()
28 {}

-----------------------------------------------------------------------我是低调的分割线-----------------------------------------------------------------------------------------
求约数个数略微复杂一点,但大体还是那个意思。
约数个数的性质,对于一个数N,N=p1^a1 + p2^a2 + ... + pn^an。其中p1 ,p2, p3... pn是N的质因数,a1 ,a2, a2,...an为相应的指数,则
                                                           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;                       //素数的约数个数为2
16         }
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 
希望大家有所收获~~                        
 Made by  M.J

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

评论

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

性能如何?
2010-04-28 17:37 | chaogu

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

线性的,复杂度在信息学竞赛中已经相当优化了。~@chaogu
2010-04-28 22:50 | M.J

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

没太看懂,lz说的求前N个数的约数个数,是指
拿1 2 3 为例
1 | 1,1 | 2,1 | 3
2 | 3,
3 | 3
结果是6?是这意思吗
2010-04-29 12:22 | schindlerlee

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

你好。这个程序是求前N个数所有数的约数的个数。拿M=100来说,程序跑完后可以得到2到100所有数的约数个数。。~@schindlerlee
2010-04-29 16:40 | M.J

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

谢谢 研究下你这个求约数个数的程序 感觉挺有用的 呵呵,如果你这个模板可以直接用就更好了哈
2010-05-03 16:20 | abilitytao

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

呵呵,应该可以做做成模板,只不过一般比赛应该不会出这么直接的题哈~!不过这个思想挺有用的,而且这几个程序确实很快。@abilitytao
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
是的。对了,这个程序的数组e[]我开小了,应该开M这么大,不是M/3.
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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理