Funkcja phi Eulera

Z RNO-Wiki
(Różnice między wersjami)
 
Linia 5: Linia 5:
  
 
<center>
 
<center>
<google>Funkcja phi Eulera</google>
+
Funkcja phi Eulera
 
</center>
 
</center>
  
Linia 12: Linia 12:
 
== Wersja ze spamiętywaniem ==
 
== Wersja ze spamiętywaniem ==
 
Dobrze jest najpierw utworzyć sobie tablicę liczb pierwszych <code>ithPrime[...]</code> indeksowaną od zera. Można to zrobić używając [[Sito Eratostenesa]].
 
Dobrze jest najpierw utworzyć sobie tablicę liczb pierwszych <code>ithPrime[...]</code> indeksowaną od zera. Można to zrobić używając [[Sito Eratostenesa]].
<table width="100%">
 
<tr>
 
<td valign="top">
 
 
<source lang="cpp">
 
<source lang="cpp">
 
const int SIZE=1000000; // rozmiar tablicy
 
const int SIZE=1000000; // rozmiar tablicy
Linia 51: Linia 48:
 
}
 
}
 
</source>
 
</source>
</td>
 
<td width="140" align="center">
 
<adsense
 
adclient="pub-2033664350513674"
 
adslot="8310283695"
 
adwidth="120"
 
adheight="240"
 
/>
 
</td>
 
</tr>
 
</table>
 
  
 
== Wersja rekurencyjna bez spamiętywania ==
 
== Wersja rekurencyjna bez spamiętywania ==
 
Tym razem nie mamy tablicy liczb pierwszych. Po prostu przeglądamy po kolei każdą liczbę <code>p</code> aż do pierwiastka z <code>n</code>.
 
Tym razem nie mamy tablicy liczb pierwszych. Po prostu przeglądamy po kolei każdą liczbę <code>p</code> aż do pierwiastka z <code>n</code>.
<table width="100%">
 
<tr>
 
<td valign="top">
 
 
<source lang="cpp">
 
<source lang="cpp">
 
long long phi(long long n) // phi Euler  function
 
long long phi(long long n) // phi Euler  function
Linia 90: Linia 73:
 
}
 
}
 
</source>
 
</source>
</td>
 
<td width="140" align="center">
 
</td>
 
</tr>
 
</table>
 
  
 
== Wersja z uzyciem tablicy <code>fDiv</code> ==
 
== Wersja z uzyciem tablicy <code>fDiv</code> ==
 
Wyliczając najpierw tablicę <code>fDiv</code> za pomocą (zob. [[Sito Eratostenesa#Znajdowanie najmniejszego dzielnika pierwszego danej liczby|Sito Eratostenesa]]) można obliczać funkcję <code>phi</code>Eulera jeszcze szybciej:
 
Wyliczając najpierw tablicę <code>fDiv</code> za pomocą (zob. [[Sito Eratostenesa#Znajdowanie najmniejszego dzielnika pierwszego danej liczby|Sito Eratostenesa]]) można obliczać funkcję <code>phi</code>Eulera jeszcze szybciej:
<table width="100%">
 
<tr>
 
<td valign="top">
 
 
<source lang="cpp">
 
<source lang="cpp">
 
int phi(int n) // phi Euler  function { n <= SIZE }
 
int phi(int n) // phi Euler  function { n <= SIZE }
Linia 123: Linia 98:
 
}
 
}
 
</source>
 
</source>
</td>
 
<td width="140" align="center">
 
<adsense
 
adclient="pub-2033664350513674"
 
adslot="8310283695"
 
adwidth="120"
 
adheight="240"
 
/>
 
</td>
 
</tr>
 
</table>
 
  
 
== Ostateczna wersja ==
 
== Ostateczna wersja ==
Linia 140: Linia 104:
 
używamy tablicy <code>fDiv[i]</code> oraz tablicy <code>ithPrime[i]</code> dla <code> 1 &lt; i &lt; 10^6 </code>.
 
używamy tablicy <code>fDiv[i]</code> oraz tablicy <code>ithPrime[i]</code> dla <code> 1 &lt; i &lt; 10^6 </code>.
  
<table width="100%">
 
<tr>
 
<td valign="top">
 
 
<source lang="cpp">
 
<source lang="cpp">
 
#include<cstdio>
 
#include<cstdio>
Linia 213: Linia 174:
 
}
 
}
 
</source>
 
</source>
</td>
 
<td width="130" align="center">
 
<adsense
 
adclient="pub-2033664350513674"
 
adslot="5958906648"
 
adwidth="120"
 
adheight="600"
 
/>
 
</td>
 
</tr>
 
</table>
 
  
 
Rafał Nowak 23:25, 2 gru 2007 (CET)
 
Rafał Nowak 23:25, 2 gru 2007 (CET)

Aktualna wersja na dzień 21:19, 21 cze 2011

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