Степень вхождения числа в факториал. c++

[Vikro]

Не могу сделать, на первый взгляд, простую задачку очень давно. Точнее решить могу, но не прохожу один из тестов по времени.
Пусть n – натуральное число. Обозначим как an максимальное натуральное число k, такое что nk – делитель n!. Например, a12 = 5, так как 125 = 248832 делит 12! = 479001600 (479001600/248832 = 1925), а 126 = 2985984 – не делит.

Задано число n. Найдите an.
Проверяю решение здесь https://acmp.ru/index.asp?main=task&id_task=978
Решить нужно именно на плюсах.
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n,an=0, st = 0;
cin >> n;
int nn = n, k = 0;
if (nn % 2 == 0){
while(nn % 2 == 0){
nn /= 2;
}
k = 2;
}
for(int i = 3; i <= nn; i+=2) {
while (nn % i == 0) {
nn = nn / i;
}
if(nn == 1) k = i;
}
nn = n;
while(nn % k == 0){
st++;
nn /= k;
}
while(n > 0){
n /= k;
an = an + n;
}
cout << an / st ;
return 0;
}
Это одно из моих решений, не проходит 9 тест.
Может ли кто-нибудь подсказать более скоростной алгоритм?
Спасибо)