Превышение времени. Разложение на простые множители - C (СИ)

Формулировка задачи:

Помогите сократить время до 0.076 мс а то у меня 2.9 с

Разложение на простые множители

Разложить число на простые множители. _________________________________________________________________________

На входе

Одна строка, содержащая целое число N в пределах 1 ≤ N ≤ 10^9(в степени 9). _________________________________________________________________________

На выходе

Произведение простых множителей и их степеней. Выводить множители нужно в порядке их возрастания (без учета степеней). _________________________________________________________________________

Пример

На вход

:123456

На выходe

:2^6 * 3^1 * 643^1

Решение задачи: «Превышение времени. Разложение на простые множители»

textual
                            Листинг программы 
                        
                            #include  <stdio.h>
 
int s(int k, int i, char c) {if (i) printf("%d^%d%c",k,i,c);}
int f(int n, int k, int i) {return
    k*k>n ? s(n,1,'\n') : k*k==n ? s(k,i+2,'\n') : n%k ? (s(k,i,'*'), f(n,k+(k<3?1:2),0)) : f(n/k,k,i+1);}
 
int main() {int n; scanf("%d",&n); f(n,2,0);}