欧拉函数模板

转载 http://www.cnblogs.com/E-star/archive/2012/08/03/2621025.html

求欧拉函数的模板：

; ;<pre>int ;euler(int ;n)//返回euler(n)

{

; ; ; ; ;int ;i;

; ; ; ; ;int ;res ;= ;n,a ;= ;n;

; ; ; ; ;for(i ;= ;2;i*i ;&lt;= ;a; ;++i)

; ; ; ; ;{

; ; ; ; ; ; ; ; ;if(a%i ;== ;0)

; ; ; ; ; ; ; ; ;{

; ; ; ; ; ; ; ; ; ; ; ; ;res ;-= ;res/i; ;//p(n) ;= ;(p ;- ;p/p1)(1 ;- ;1/p2)......

; ; ; ; ; ; ; ; ; ; ; ; ;while(a%i ;== ;0) ;a/=i;

; ; ; ; ; ; ; ; ;}

; ; ; ; ;}

; ; ; ; ;if(a ;&gt; ;1) ;res ;-= ;res/a;//存在大于sqrt(a)的质因子

; ; ; ; ;return ;res;

}</pre> ; ;

欧拉函数打表：

; ;<pre>void ;SE()//select ;euler//类似于素数筛选法

{

; ; ; ;int ;i,j;

; ; ; ;euler[1] ;= ;1;

; ; ; ;for(i ;= ;2;i ;&lt; ;Max; ;++i) ; ;euler[i]=i;

; ; ; ;for(i ;= ;2;i ;&lt; ;Max; ;++i)

; ; ; ;{

; ; ; ; ; ; ; ; ;if(euler[i] ;== ;i)//这里出现的肯定是素数

; ; ; ; ; ; ; ; ;{

; ; ; ; ; ; ; ; ; ; ;for(j ;= ;i; ;j ;&lt; ;Max; ;j ;+= ;i)//然后更新含有它的数

; ; ; ; ; ; ; ; ; ; ;{

; ; ; ; ; ; ; ; ; ; ; ; ; ;euler[j] ;= ;euler[j]/i*(i ;- ;1); ;// ;n*(1 ;- ;1/p1)....*(1 ;- ;1/pk).先除后乘

; ; ; ; ; ; ; ; ; ; ;}

; ; ; ; ; ; ; ;}

; ; ; ;}

; ; ; ; ;//for ;(int ;i ;= ;1; ;i ;&lt;= ;20; ;++i) ;printf("%d ;",euler[i]);

}</pre> ; ;