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
Podziękował: 3 razy

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

Post autor: anusiakk »

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:

\(\displaystyle{ \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
Pomógł: 20 razy

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

Post autor: Ralf1410 »

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
Użytkownik
Użytkownik
Posty: 4819
Rejestracja: 10 paź 2006, o 23:03
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 43 razy
Pomógł: 1407 razy

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

Post autor: Szemek »

\(\displaystyle{ \varphi (1234567) = \varphi (127) \cdot \varphi (9721) = 126 \cdot 9720}\)
ODPOWIEDZ