歐拉函式(Euler函式)

歐拉函式

Euler函式一般指本詞條

數論,對正整數n,歐拉函式是小於n的正整數中與n互質的數的數目(φ(1)=1)。此函式以其首名研究者歐拉命名(Euler's totient function),它又稱為Euler's totient function、φ函式、歐拉商數等。 例如φ(8)=4,因為1,3,5,7均和8互質。 從歐拉函式引伸出來在環論方面的事實和拉格朗日定理構成了歐拉定理的證明。

基本介紹

  • 中文名:歐拉函式
  • 外文名:Euler's totient function
  • 定義:小於n的數中與n互質的數的數目
  • 發現人:歐拉(Euler)
函式內容,證明,編程實現,C++版,pascal版,C語言,Java語言,C#語言,函式表,

函式內容

通式:
其中p1, p2……pn為x的所有質因數,x是不為0的整數。
φ(1)=1(和1互質的數(小於等於1)就是1本身)。
注意:每種質因數隻一個。 比如12=2*2*3那么φ(12)=φ(4*3)=φ(2^2*3^1)=(2^2-2^1)*(3^1-3^0)=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.若a為質數,phi[a]=a-1;2.若a為質數,b mod a=0,phi[a*b]=phi[b]*a3.若a,b互質,phi[a*b]=phi[a]*phi[b](當a為質數時,if b mod a!=0 ,phi[a*b]=phi[a]*phi[b])*/int m[n],phi[n],p[n],nump;//m[i]標記i是否為素數,0為素數,1不為素數;p是存放素數的數組;nump是當前素數個數;phi[i]為歐拉函式int main(){        phi[1]=1;    for (int i=2;i<=n;i++)    {        if (!m[i])//i為素數        {            p[++nump]=i;//將i加入素數數組p中            phi[i]=i-1;//因為i是素數,由特性得知            }            for (int j=1;j<=nump&&p[j]*i<=n;j++)  //用當前已得到的素數數組p篩,篩去p[j]*i        {            m[p[j]*i]=1;//可以確定i*p[j]不是素數             if (i%p[j]==0) //看p[j]是否是i的約數,因為素數p[j],等於判斷i和p[j]是否互質             {                phi[p[j]*i]=phi[i]*p[j]; //特性2                break;            }            else phi[p[j]*i]=phi[i]*(p[j]-1); //互質,特性3其,p[j]-1就是phi[p[j]]           }    }}

pascal版

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(maxn) 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語言

#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語言

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;    }}

C#語言

using System;using System.Collections.Generic;public class Program{    public static void Main(string[] args)    {        Console.Write("輸入一個整數:");        long num = long.Parse(Console.ReadLine());        long a = num;        double oulaAnwser = 0;        List<long> oulaList = new List<long>();        if (IsPrime(num))        {            oulaAnwser = num - 1;        }        else        {            List<long> allPrime = GetAllPrime(num);            foreach (long i in allPrime)            {                long tem = num;                num = Repeatdivide(num, i);                if (tem != num)                {                    oulaList.Add(i);                }            }            oulaAnwser = a;            foreach (long j in oulaList)            {                oulaAnwser = oulaAnwser * (1 - (double)1 / j);            }        }        Console.WriteLine("歐拉函式的值為" + Math.Round(oulaAnwser));        Console.ReadLine();    }    public static List<long> GetAllPrime(long num)    {        List<long> result = new List<long>();        for (long i = 2; i < num; i++)        {            if (IsPrime(i))            {                result.Add(i);            }        }        return result;    }    public static bool IsPrime(long num)    {        if (num < 2)        {            return false;        }        for (long i = 2; i <= Math.Sqrt(num); i++)        {            if (num % i == 0)            {                return false;            }        }        return true;    }    public static bool CanbeDivide(long num, long i)    {        return num == 1 ? false : num % i == 0 ? true : false;    }    public static long Repeatdivide(long num, long i)    {        long result = 0;        if (CanbeDivide(num, i))        {            result = Repeatdivide(num / i, i);        }        else        {            return num;        }        return result;    }}

函式表

0~100歐拉函式表(“x?”代表十位數,“x”代表個位數)
φ(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)=16

相關詞條

熱門詞條

聯絡我們