Sposoby rozłożenia funkcji Eulera

[BigPaws]

Pogooglowałem trochę ale nie znalazłem dobrego przepisu. Radze sobie z mniejszymi funkcjami Eulera, znam zasady, wzory, wiem, że musze rozłożyć na czynniki które są względnie pierwsze ale czy jest jakiś przepis na szukanie ich czy jest to metoda prób i błędów? Na kolokwium ostatnio poległem bo za dużo czasu zostawałem na zadaniach z Eulerem, dlatego szukam jakiegoś szybkiego sposobu.

[PoweredDragon]

Wydaje mi się, że prostym sposobem jest rozłożenie f. Eulera na czynniki będące potęgami liczb pierwszych.

Np. \(\displaystyle{ x = 2^{\alpha_1} \cdot 3^{\alpha_2} \cdot 5^{\alpha_3} \cdot ...}\)
\(\displaystyle{ \phi(x) = \phi(2^{\alpha_1}) \cdot \phi(3^{\alpha_2}) \cdot \phi(5^{\alpha_3}) \cdot ...}\)

Jeśli dostaniesz jakąś chorą liczbę, to zrób test pierwszości(szukanie czynników mniejszych od pierwiastka) liczby i raczej łatwo znajdziesz czynnik, przez który możesz przedzielić. Jak znajdziesz wszystkie czynniki, to rozłożenie na iloczyn f. Eulera od każdego z czynników pierwszych do pewnej potęgi jest już proste.

Przy znacznie bardziej chorych liczbach to mogą się pojawiać problemy, ale to chyba każdy takie może mieć ;v

[BigPaws]

No do tysiąca i okolic nie ma problemu, ale jak dostajesz liczbę 5cyfrową i przy rozkładaniu na czynniki pierwsze szukasz liczby pierwszej już powyżej 20 to zajmuje sporo czasu

[PoweredDragon]

No niestety; jak się uweźmie wykładowca to i 10-cyfrową może dać pierwszą i szukaj sobie czynników, niestety nie wiem czy jest jakiś algorytm szybszy do rozkładania dużych liczb na czynniki pierwsze ;v