factorial zeroes 2

main.cpp

#include <iostream>
#include <ctime> 

int CountZeroes(int n);
int CountFivesInFactorization(int n);
bool IsPrime(int n); 

int main()
{
    int n = 0;
    while (n >= 0)
    {
        std::cout << "enter value for n, -1 to quit: ";
        std::cin >> n;
        if (n < 0)
            break;
        clock_t time = clock();
	std::cout << "zeroes at the end of " << n 
                  << "!: " << CountZeroes(n);
        time = clock() - time;
        std::cout << " - operation took "
                  << (time * 1000) / CLOCKS_PER_SEC 
                  << "ms" << std::endl;
    } 
    return 0;
} 

//counts the number of zeroes at the end of n!
int CountZeroes(int n)
{
    if (n < 5)
        return 0; 

    int fives = 1;
    int i = 10;
    while (i <= n)
    {
        //i is already a multiple of 5, skip that step
        fives += 1 + CountFivesInFactorization(i/5);
        i += 5;
    }
    return fives;
}

//counts the number of fives in the prime factorization of n
int CountFivesInFactorization(int n)
{
    if (IsPrime(n))
        return n == 5 ? 1 : 0;      

    for (int i = 2; i*i <= n; i++)
    {
        if (n % i == 0)
        {
            int result = n / i;
            int fives = 0;

            if (IsPrime(result))
            {
                if (result == 5)
                    fives++;
            }
            else
                fives += CountFivesInFactorization(result); 

            if (IsPrime(i))
            {
                if (i == 5)
                    fives++;
            }
            else
                fives += CountFivesInFactorization(i); 

            return fives;
        }
    }
    return 0;
}

//returns true if n is prime
bool IsPrime(int n)
{
    if (n == 1)
        return false;
    if (n == 2)
        return true;      

    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}