Tocjent

Definicja

Tocjent jest to funkcja, która przyporządkowuje każdej liczbie naturalnej liczbę liczb względnie z nią pierwszych. Warunkiem jest, aby znalezione liczby względnie pierwsze były nie większe od argumentu funkcji. Funkcja jest oznacza przez . W celu obliczenia funkcji dla dowolnego argumentu n można się posłużyć poniższym wzorem:

W podanym wzorze liczby są wszystkimi, różnymi czynnikami pierwszymi liczby n.

Implementacja prosta

Założenia

Najprostszy sposób wyliczenia funkcji dla dowolnego argumentu jest znalezienie wszystkich liczb względnie pierwszych z zakresu [1, n]. Dokładny opis znajdowania liczb względnie pierwszych można przeczytać tutaj. W tym przypadku wystarczy funkcja znajdowania NWD:

1. int nwd(int a, int b) {
2.   return (a == 0) ? b : nwd(b % a, a);
3. }

Jeśli funkcja nwd() zwróci dla i-tej liczby oraz n 1 to liczby będą względnie pierwsze.

Główna funkcja

1. int phi(int n) {
2.   int licznik = 0;
3.   for (int i = 1; i <= n; i++) {
4.     if (nwd(i, n) == 1)
5.       licznik++;
6.   }
7.   return licznik;
8. }

(1.) Funkcji phi() przyjmuje jeden argument n. (2.) Inicjalizacja licznika i ustawienie wartości początkowej 0. (3.) Dla każdej liczby z zakresu [1, n]: (4.) sprawdź czy jest względnie pierwsza z n i (5.) zwiększ licznik. Po zakończeniu pętli for (7.) zwróć wynik licznik.

Wykorzystanie wzoru

Funkcję Tocjent można też napisać również w wersji iteracyjnej, ale wykorzystując wzór. W tym celu należy znaleźć z ilu różnych liczb pierwszych składa się liczba n. Zadanie to realizuje poniższy kod:

1. int phi(int n) {
2.   double suma = n;
3.   int dzielnik = 2;
4.   while (n != 1) {
5.     while (n % dzielnik != 0)
6.       dzielnik++;
7.     suma *= (1 - 1.0 / dzielnik);
8.     while (n % dzielnik == 0) {
9.       n /= dzielnik;
10.     } 
11.   }
12.   return int(suma);
13. }

(2.) Początkowo suma wynosi n. Dopiero po znalezieniu liczby pierwszej suma będzie mnożona. (3.) Najmniejsza liczba pierwsza to 2. (3.) Jeśli liczba n jest różna od 1 to: (4. - 5.) znajdź kolejny dzielnik liczby, (6.) pomnóż sumę przez kolejną wartość i (7. - 8.) usuń wszystkie wystąpienia znalezionego czynnik dzielnik. Ze względu na fakt, że funkcja za każdym razem pozbywa się wszystkich wystąpień dzielnik gwarantowane jest, że następny dzielnik będzie liczbą pierwszą. Na koniec (10.) zwracana jest część całkowita zmiennej suma.

Testowanie funkcji

Obydwie implementacji funkcji phi() można przetestować przy pomocy poniższej funkcji main():

1. int main () {
2.   for (int i = 1; i <= 10; i++) {
3.     cout << "phi(" << i << ")=" << phi(i) << endl;
4.   }
5.   system("pause");
6.   return 0;
7. }

• Kod źródłowy Prosta implementacja
• Kod źródłowy Wykorzystanie wzoru

Ćwiczenia

Zadanie 1

Napisz program, który wczyta od użytkownika trzy liczby: a, b i s. Program powinien wypisać wszystkie argumenty tj. liczby naturalne z zakresu [a, b], których wartość funkcji phi(n) wynosi s.

Przykładowo dla danych:

1. 1 10 2

Program wypisze na ekran:

1. 3 4 6

• Kod źródłowy Zadanie 1