Funkcja phi Eulera

Z RNO-Wiki

Spis treści

Definicja

Funkcja <math>\varphi(n)</math> Eulera jest zdefiniowana następująco

 phi(n) = liczba liczb mniejszych od n względnie pierwszych z n

Funkcja phi Eulera

Implementacja w C/C++

Wersja ze spamiętywaniem

Dobrze jest najpierw utworzyć sobie tablicę liczb pierwszych ithPrime[...] indeksowaną od zera. Można to zrobić używając Sito Eratostenesa.

const int SIZE=1000000; // rozmiar tablicy
int SIZE_P=75000;       // oszacowana liczba liczb pierwszych
 
vector<bool> isPrime(SIZE+1);  // tablica wartości logicznych
vector<int>  ithPrime(SIZE_P); // tablica kolejnych liczb pierwszych
 
long long phi_tab[1000000];
 
long long phi(long long n) // phi Euler  function
{
	long long nn = n;
	if (n<=1) return n;
	if (n==2) return 1;
	if (nn < 1000000 && phi_tab[nn]) return phi_tab[nn];
	long long wynik = 1, p;
 
	for (int i=0; i<SIZE_P; i++)
	{
		p = ithPrime[i];
		if (n%p==0)
		{
			long long q=1, qq=p;
			n /= p;
			while (n%p==0)
			{
				q=qq; qq = qq*p;
				n = n/p;
			}
			wynik *= qq-q;
		}
	}
	if (nn < 1000000) phi_tab[nn] = wynik;
	return wynik;
}

Wersja rekurencyjna bez spamiętywania

Tym razem nie mamy tablicy liczb pierwszych. Po prostu przeglądamy po kolei każdą liczbę p aż do pierwiastka z n.

long long phi(long long n) // phi Euler  function
{
	if (n<=1) return n;
	if (n==2) return 1LL;
	for (long long p=2; p*p<=n; p++)
	{
		if (n%p==0)
		{
			long long q=1, qq=p;
			n /= p;
			while (n%p==0)
			{
				q=qq; qq = qq*p;
				n = n/p;
			}
			return (qq-q)*phi(n);
		}
	}
	return n-1;
}

Wersja z uzyciem tablicy fDiv

Wyliczając najpierw tablicę fDiv za pomocą (zob. Sito Eratostenesa) można obliczać funkcję phiEulera jeszcze szybciej:

int phi(int n) // phi Euler  function { n <= SIZE }
{
	if (n<=1) return n;
	if (n==2) return 1;
	int wynik = 1, p, q, qq;	
 
	while(n>1)
	{
		p = fDiv[n]; // z tego powodu n musi byc małe
		q=1, qq=p;
		n /= p;
		while (n%p==0)
		{
			q=qq; qq = qq*p;
			n = n/p;
		}
		wynik *= qq-q;
	}
	return wynik;
}

Ostateczna wersja

Ponieżej zamieszczam kod obliczania funkcji Eulera phi(n), który działa dla 1 < n < 10^12 . Dla małych wartości, tj. dla n < 10^6 używane jest spamiętywanie. Natomiast dla pozostałych wartości n, używamy tablicy fDiv[i] oraz tablicy ithPrime[i] dla 1 < i < 10^6 .

#include<cstdio>
#include<vector>
using namespace std;
 
const int SIZE=1000000; // rozmiar tablicy
vector<int> fDiv(SIZE+1);
vector<int> ithPrime;
/*
	fDiv - cel
	{  fDiv[n] = najmniejszy dzielnik pierwszy liczby n  }
*/
 
/* Procedura obliczająca tablicę fDiv i ithPrime za pomocą metody sita Eratostenesa */
void makeTable()
{
	for (int i=2; i<=SIZE; i++) fDiv[i] = i;
 
	for (int i=2; i*i<=SIZE; i++)
		if (fDiv[i]==i)
			for (int j=i*i; j<=SIZE; j=j+i)
				if ( fDiv[j]==j ) fDiv[j]=i;
 
	for(int p = 2; p <= SIZE; p++) if (fDiv[p]==p) ithPrime.push_back(p);
}
 
long long phi_tab[SIZE+1];
long long phi(long long n) // phi Euler function
{
	long long nn = n, wynik = 1, p,q,qq;
	if (n<=1) return n;
	if (n==2) return 1;
	if (nn < 1000000 && phi_tab[nn]) return phi_tab[nn];
 
	int i=0;
	while (n>1)
	{
		if (n<=SIZE) p = fDiv[n];
		else
		{
			// szukamy dzielnika pierwszego liczby n
			while(i<ithPrime.size() && n%(p=ithPrime[i])!=0) i++;
			if (i==ithPrime.size()) p = n; // n jest pierwsza
		}
 
		q=1, qq=p;
		n /= p;
		while (n%p==0)
		{
			q=qq; qq = qq*p;
			n = n/p;
		}
		wynik *= qq-q;
	}
	if (nn < 1000000) phi_tab[nn] = wynik;
	return wynik;
}
 
 
int main(void)
{
	makeTable();
	while(true)
	{
		long long n;
		scanf("%lld", &n);
		printf("%lld\n", phi(n));
	}
}

Rafał Nowak 23:25, 2 gru 2007 (CET)

Osobiste