<dl class="lemmaWgt&#45;lemmaTitle lemmaWgt&#45;lemmaTitle&#45;"> <dd class="lemmaWgt&#45;lemmaTitle&#45;title">

欧拉函数

</dd> </dl>
在 数论，对 正整数n， 欧拉函数是小于n的正整数中与n 互质的数的数目（φ(1)=1）。此函数以其首名研究者欧拉命名(Euler’so totient function)，它又称为Euler’s totient function、 φ函数、欧拉 商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和 拉格朗日定理构成了 欧拉定理的证明。
<dl><dt class="basicInfo&#45;item name"> 定    义 </dt> <dd class="basicInfo&#45;item value"> 小于n的数中与n 互质的数的数目 </dd> <dt class="basicInfo&#45;item name"> 发现人 </dt> <dd class="basicInfo&#45;item value"> 欧拉(Euler) </dd>

目录

  1. ▪ 简介
  2. 1 证明
  3. 2 编程实现
  1. ▪ C++版
  2. ▪ pascal版
  3. ▪ C语言
  1. ▪ Java语言
  2. 3 函数表

欧拉函数简介

通式：
其中p1, p2……pn为x的所有质因数，x是不为0的整数。
φ(1)=1（唯一和1 互质的数(小于等于1)就是1本身）。
注意：每种质因数只一个。 比如12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4
若n是质数p的k次幂，
，因为除了p的倍数外，其他数都跟n互质。
设n为正整数，以 φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值
φ：N→N，n→φ(n)称为欧拉函数。
欧拉函数是 积性函数——若m,n互质，
特殊性质：当n为奇数时，
, 证明与上述类似。
若n为质数则

欧拉函数证明

编辑
设A, B, C是跟m, n, mn互质的数的集，据中国 剩余定理，A*B和C可建立一一对应的关系。因此φ(n)的值使用 算术基本定理便知，
若
则
例如
与欧拉定理、 费马小定理的关系
对任何两个互质的正整数a, m(m>=2)有
即欧拉定理
当m是质数p时，此式则为：
即费马小定理。

欧拉函数编程实现

编辑
利用欧拉函数和它本身不同质因数的关系，用 筛法计算出某个范围内所有数的欧拉函数值。
欧拉函数和它本身不同质因数的关系：
欧拉函数ψ（N）=N{∏p|N}（1－1/p）
亦即:
（P是数N的 质因数）
如：
ψ（10）=10×（1－1/2）×（1－1/5）=4；
ψ（30）=30×（1－1/2）×（1－1/3）×（1－1/5）=8；
ψ（49）=49×（1－1/7）=
=42。

欧拉函数C++版

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*线性筛O(n)时间复杂度内筛出maxn内欧拉函数值*/
int  m[maxn],phi[maxn],p[maxn],pt; //m[i]是i的最小素因数，p是素数，pt是素数个数
 
int  make()
{
     phi[1]=1;
     int  N=maxn;
     int  k;
     for ( int  i=2;i<N;i++)
     {
         if (!m[i]) //i是素数
             p[pt++]=m[i]=i,phi[i]=i-1;
         for ( int  j=0;j<pt&&(k=p[j]*i)<N;j++)
         {
             m[k]=p[j];
             if (m[i]==p[j]) //为了保证以后的数不被再筛，要break
             {
                 phi[k]=phi[i]*p[j];
/*这里的phi[k]与phi[i]后面的∏(p[i]-1)/p[i]都一样（m[i]==p[j]）只差一个p[j]，就可以保证∏(p[i]-1)/p[i]前面也一样了*/
                 break ;    
             }
             else
                 phi[k]=phi[i]*(p[j]-1); //积性函数性质，f(i*k)=f(i)*f(k)
         }
     }
}

欧拉函数pascal版

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
const
     maxn = 10000 ;
     sqrtn = trunc(sqrt(maxn));
var
     i,j,n,si:longint;
     fi:array[ 1. .maxn] of longint;
     hash :array[ 1. .sqrtn] of boolean;
     ssb:array[ 1. .sqrtn] of longint;
procedure yuchuli;
var
     i,j,daili:longint;
     pd:boolean;
begin
     fillchar( hash ,sizeof( hash ),false);
     i: = 2 ;
     si: = 0 ;
     while  i< = sqrt(n) do
     begin
         if  not  hash [i] then
         begin
             for  j: = i + 1  to sqrt(ndivi) do  hash [i * j]: = true;
             inc(si);
             ssb[si]: = i;
         end;
         inc(i);
     end;
     for  i: = 1  to maxn do fi[i]: = 1 ;
     for  i: = 2  to maxn do
     begin
         daili: = i;
         for  j: = 1  to si do
         begin
             pd: = false;
             while  daili mod ssb[j] = 0  do
             begin
                 daili: = daili div ssb[j];
                 if  not  pd then fi[i]: = fi[i] * (ssb[j] - 1 )
                 else  fi[i]: = fi[i] * ssb[j];
                 pd: = true;
             end;
         end;
         if  daili<> 1  then fi[i]: = fi[i] * (daili - 1 );
     end;
end;
begin
     yuchuli;
     readln(n);
     writeln(fi[n]);
end.

欧拉函数C语言

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
#include<stdlib.h>
int  eular( int  n)
{
     int  ret=1,i;
     for (i=2;i*i<=n;i++)
     {
         if (n%i==0)
         {
             n/=i,ret*=i-1;
             while (n%i==0) n/=i,ret*=i;
         }
     }
     if (n>1) ret*=n-1;
     return  ret;
}
int  main ()
{
       int  n,s;
       scanf ( "%d" ,&n);
       s=eular(n);
       printf ( "%d" ,s);
       return  0;
}

欧拉函数Java语言

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import  java.util.ArrayList;
import  java.util.List;
import  java.util.Scanner;
 
public  class  Oula {
     public  static  void  main(String[] args){
         Scanner scanner= new  Scanner(System.in);
         int  num=scanner.nextInt();
         int  a=num;
         double  oulaAnwser= 0 ;
         ArrayList<Integer> oulaList =  new  ArrayList<Integer>();
         if  (isPrime(num)){
             oulaAnwser=num- 1 ;
         } else {
             List<Integer> allPrime = getAllPrime(num);
             for ( int  i : allPrime){
                 int  tem=num;
                 num=repeatdivide(num,i);
                 if  (tem!=num){
                     oulaList.add(i);
                 }
             }
             oulaAnwser=a;
             for  ( int  j :oulaList){
                  oulaAnwser=oulaAnwser*( 1 -( double ) 1 /j);
             }
         }
         System.out.println( "欧拉函数的值为" +Math.round(oulaAnwser));
     }
     public  static  List<Integer> getAllPrime( int  num){
         ArrayList<Integer> result =  new  ArrayList<Integer>();
         for  ( int  i = 2 ;i<num;i++){
             if  (isPrime(i)) {
                 result.add(i);
             }
         }
         return  result;
     }
     public  static  boolean  isPrime( int  num){
         if (num <  2 ) {
             return  false ;
         }
         for ( int  i =  2 ; i <= Math.sqrt(num); i++ ) {
             if (num%i ==  0 ) {
                 return  false ;
             }
         }
         return  true ;
     }
 
     public  static  boolean  canbedivide( int  num, int  i ){
         return  num== 1 ? false :num%i== 0 ? true : false ;
     }
     public  static  int  repeatdivide( int  num, int  i ){
         int  result= 0 ;
         if  (canbedivide(num,i)){
             result=repeatdivide(num/i,i);
         } else {
             return  num;
         }
         return  result;
     }
}

欧拉函数函数表

编辑
<caption> 0~100欧拉函数表（“x?”代表十位数，“x”代表个位数）
　　 </caption>
φ(n) 0 1 2 3 4 5 6 7 8 9
0? 0 1 1 2 2 4 2 6 4 6
1? 4 10 4 12 6 8 8 16 6 18
2? 8 12 10 22 8 20 12 18 12 28
3? 8 30 16 20 16 24 12 36 18 24
4? 16 40 12 42 20 24 22 46 16 42
5? 20 32 24 52 18 40 24 36 28 58
6? 16 60 30 36 32 48 20 66 32 44
7? 24 70 24 72 36 40 36 60 24 78
8? 32 54 40 82 24 64 42 56 40 88
9? 24 72 44 60 46 72 32 96 42 60
φ(100)=40
词条标签：
<dd id="open&#45;tag&#45;item"> 科技术语 ， 科学 ， 数学 ， 学科 </dd>
</dl>