欧拉模板

 1 const MAX=1000000;
 2 var   Prime:array[0..MAX] of longint;
 3       v:array[0..MAX] of boolean;
 4  
 5       procedure GetPrime;
 6       var   i,j,tmp,size:longint;
 7       begin
 8             size:=0;
 9             fillchar(v,sizeof(v),0);
10             for i:=2 to MAX do
11             begin
12                   if not v[i] then
13                   begin
14                         inc(size);
15                         prime[size]:=i;
16                   end;
17                   j:=1;
18                   while (j<=size)and(prime[j]*i<MAX) do
19                   begin
20                         v[i*prime[j]]:=true;
21                         if i mod prime[j]=0 then break;
22                         inc(j);
23                   end;
24             end;
25       end;
26  
27 begin
28       GetPrime;
29 end.
30 它在O(N)的时间内遍历了所有的数,并且有很多的附加信息,
31 
32 那么我们是不是能在筛素数的同时求出所有数的欧拉函数呢.
33 
34 答案是可以.
35 
36 1.对于筛出来的素数,φ(P)=P-1.
37 
38 在while循环内
39 
40 2.若i mod prime[j]=0,那么φ(i*prime[j])=φ(i)*prime[j]
41 
42 3.若i mod prime[j]≠0,那么φ(i*prime[j])=φ(i)*(prime[j]-1)
43 
44 2,3请读者自己证明,其中3用到了欧拉函数的积性.
45 
46 code:
47 
48 const MAX=1000000;
49 var   Phi,Prime:array[0..MAX] of longint;
50       v:array[0..MAX] of boolean;
51  
52       procedure GetPrime;
53       var   i,j,tmp,size:longint;
54       begin
55             size:=0;
56             fillchar(v,sizeof(v),0);
57             for i:=2 to MAX do
58             begin
59                   if not v[i] then
60                   begin
61                     inc(size);
62                         prime[size]:=i;
63                         phi[i]:=i-1;
64                   end;
65                   j:=1;
66                   while (j<=size)and(prime[j]*i<MAX) do
67                   begin
68                         tmp:=i*prime[j];
69                         v[tmp]:=true;
70                         if i mod prime[j]=0 then
71                         begin
72                               phi[tmp]:=phi[i]*prime[j];
73                               break;
74                         end
75                         else phi[tmp]:=phi[i]*(prime[j]-1);
76                         inc(j);
77                   end;
78             end;
79       end;
80  
81 begin
82       GetPrime;
83 end.

View Code

欧拉函数用希腊字母φ表示,φ(N)表示N的欧拉函数.

对φ(N)的值,我们可以通俗地理解为小于N且与N互质的数的个数.

欧拉函数的一些性质:

1.欧拉函数是积性函数,但不是完全积性函数,即φ(mn)=φ(n)*φ(m)只在(n,m)=1时成立.

2.对于一个正整数N的素数幂分解N=P1^q1*P2^q2*...*Pn^qn.

φ(N)=N*(1-1/P1)*(1-1/P2)*...*(1-1/Pn).

3.除了N=2,φ(N)都是偶数.

4.设N为正整数,∑φ(d)=N (d|N).

根据性质2,我们可以在O(sqrt(n))的时间内求出一个数的欧拉函数值.