1927. Funkcja phi Eulera [EULER_PH]

[kokosek_sof1]

Mógłby ktoś podpowiedzieć, jak zrobić to zadanie?
Próbowałem wyznaczyć liczby pierwsze tą najwolniejszą metodą, czyli:

for(i=2;i<j;i++)
if(j%i==0)puts("j nie jest pierwsze");

ale oczywiście złożoność kwadratowa (jeśli by sprawdzać wszystkie liczby do tej podanej w zadaniu), więc TLE.
Potem próbowałem jakoś ścisnąć te liczby w tablicy za pomocą sita Eratostenesa, ale skoro liczby mogą być do 2*10^9, to nawet po pominięciu parzystych się to nie uda.
Tak więc pewnie najlepszym sposobem jest ten oto wzór:

gdzie p1, p2, ... , p_k są wszystkimi czynnikami pierwszymi liczby n liczonymi bez powtórzeń.
Zna ktoś [szybki] algorytm na znajdywanie dzielników pierwszych albo inny algorytm rozwiązujące to zadanie?

[m_sasinowski1]

Zeby znalezc rozklad liczby n na czynniki pierwsze potrzebujemy czasu rzedu:
Niech x = sqrt(n). Wtedy mozna to zrobic uzywajac zlozonosci:
O(x + x * lg(x)).

[kokosek_sof1]

Znaczy wiem, że można znaleźć dzielniki liczby w czasie sqrt(liczba), ale rozłożyć na czynniki już nie umiem chyba.
Bo np. mamy liczbę 252198.
No i można tak wypisać dzielniki tej liczby:

(kiedyś tu był kod  ;-) )

ale to nie rozłoży nam na czynniki pierwsze liczbę, tylko wypisze jej dzielniki.
Np. dla 20 wypisze: 2, 4, 5, 10 zamiast 2, 2, 5
No więc trzeba by tak zrobić na przykład:

(tu też był kod)

Jednak nie jest to chyba złożoność logarytmiczna (tak czy inaczej to też dostaje TLE).

//Edit:
Ok, znalazłem, co zrobić. No więc należy sprawdzać do sqrt(liczba) dzielniki pierwsze, a potem to, co zostanie, to kolejny dzielnik pierwszy tej liczby, chyba że... no i tutaj sami dojdźcie.

[novy665]

Na początku myslałem, że wystarczy sqrt (max n), ale nie.
10^6 na przykład, ale dalej WA.

[narbej]

Gratuluję
A przy okazji, to zadanie http://www.spoj.pl/problems/DIVSUM/ na międzynarodowym, jest dość podobne - tylko zamiast iloczynu dzielników będących liczbami pierwszymi jest suma wszystkich niepowtarzalnych dzielników danej liczby.