Funkcja Eulera - jak ja obliczyć w przypadku dużych liczb ?

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
anusiakk
Użytkownik
Użytkownik
Posty: 34
Rejestracja: 24 lut 2009, o 15:47
Płeć: Mężczyzna

Funkcja Eulera - jak ja obliczyć w przypadku dużych liczb ?

Post autor: anusiakk » 19 kwie 2009, o 21:34

Czy istnieje jakiś sposób, dobra metoda, aby obliczyć wartość funkcji Eulera dla dużych liczb ? Np., jak obliczyć coś takiego, w miarę szybki sposób: \(\varphi(1234567)=?\) Czy jednak muszę postepować jak w przypadku mniejszych liczb i rozkładać na liczby pierwsze? Prosze o pomoc.

Ralf1410
Użytkownik
Użytkownik
Posty: 116
Rejestracja: 5 kwie 2009, o 21:36
Płeć: Mężczyzna

Funkcja Eulera - jak ja obliczyć w przypadku dużych liczb ?

Post autor: Ralf1410 » 19 kwie 2009, o 21:57

Chyba metoda z rozkładem na liczby pierwsze jest jedyną możliwą, ale do rozkładu większych liczb stosuje się z tego co wiem komputery.

Awatar użytkownika
Szemek
Gość Specjalny
Gość Specjalny
Posty: 4819
Rejestracja: 10 paź 2006, o 23:03
Płeć: Mężczyzna
Lokalizacja: Gdańsk

Funkcja Eulera - jak ja obliczyć w przypadku dużych liczb ?

Post autor: Szemek » 19 kwie 2009, o 23:46

\(\varphi (1234567) = \varphi (127) \cdot \varphi (9721) = 126 \cdot 9720\)

ODPOWIEDZ