Se citeste de la tastatura un numar natural, n (n in [1,10^9]), si se cere sa se scrie in fisierul text bac.txt cel mai mare numar natural p cu proprietatea ca numarul 45^p este divizor al numarului obtinut prin evaluarea produsului 123*...*n.
Proiectati un algoritm eficient din punctul de vedere al timpului de executare si al memoriei utilizate.
Exemplu: daca n=14, fisierul contine numarul 2 (45^2=2025 este divizor al lui 123*...*14=87178291200).
- Date de intrare
- Se citeste de la tastatura numarul natural n.
- Date de iesire
- Se scrie in fisierul bac.txt cel mai mare p astfel incat 45^p divide n!.
- Restrictii
- 1 <= n <= 10^9
Exemple
Exemplul 1
Intrare
14
Iesire
2
Exemplul 2
Intrare
1
Iesire
0