Algorithms

// Calculate the least significant (non-zero) digits of large factorials.
// By Robert C. Cartaino
// Posted via http://www.codeproject.com
// 02-July-2008

using System;

class Program
{
    const ulong Target = 1000000;       // This is the number you are trying to find the factorial of.
    const ulong RoundOff = 10000000000; // This rounds off the answer so the intermediate results don't overflow.

    static void Main(string[] args)
    {
        ulong factorial = 1;

        // Iterate through all numbers up to 'Target', multiply by each to find the factorial of 'Target'.
        for (ulong n = 1; n <= Target; n++)
        {
            factorial *= n;

            // Remove the trailing zeros.
            while (factorial % 10 == 0)
            {
                factorial /= 10;
            }

            // We only need the right-most digits.
            factorial %= RoundOff;

            //Console.WriteLine("{0}! = {1}", n, factorial);
        }

        Console.WriteLine("{0}! (truncated) = {1}", Target, factorial);
    }
}

Ian Uy wrote:

I'm lost on how to begin to tackle this problem. Please advice.

Ian Uy wrote:

I have always been really stupid in basic math.

int main()
{
	int InputCase;
	cin >> InputCase;

		for(int i=2;i<=InputCase;i++)
		{
			if(InputCase%i==0)
			{
				//cout << InputCase << "/" << i << "=" << InputCase/i << endl;
				cout << i;
				InputCase/=i;
				i--;
			}
		}
	

	return 0;
}

Ian Uy wrote:

Yup, for some reason it did threw the right answers.

Robert.C.Cartaino wrote:

As a college student, you really should be able to do this. It's basic math.

MarkBrock wrote:

my bet is 99% of college students don't know (or care) how to do this, along with 99% of the rest of the world.

MarkBrock wrote:

To be fair, my bet is 99% of college students don't know (or care) how to do this, along with 99% of the rest of the world.

ChandraRam wrote:

You must have been taught how at junior school, though

Member 4194593 wrote:

You do not need to divide by all numbers, only by primes.

Ian Uy wrote:

That's why its so slow at 20!.

void prime_factors(unsigned int n, std::deque<std::pair<unsigned int,unsigned int>>& factor_list)
{
   factor_list.clear();

   unsigned int upper_bound = ::floor(std::sqrt(n));
   unsigned int i = 2;
   while(i <= upper_bound)
   {
      std::pair<unsigned int, unsigned int> current_factor(i,0);
      while(0 == (n % i))
      {
         n /= i;
         ++current_factor.second;
      }
      if (current_factor.second > 0)
      {
         factor_list.push_back(current_factor);
      }
      ++i;
   }
}