Algorithms

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;
   }
}

int main()
{	
int InputCase;	
cin >> InputCase;
for(int i=2;i<=InputCase;i++)
   {
   if(InputCase%i==0)
      {
      cout << i;
      InputCase/=i;
      i--;
      }
   }
return 0;
}

if(InputCase%i==0)

if (n % 2 == 0) n++;
while(!is_prime(n)) { ++n; }

if(InputCase%i==0)

cp9876 wrote:

The most important thing he should do is limit the testing to sqrt(N).

Arash Partow wrote:

I believe this is not correct, assume you have an x composed from 2p where p is a prime, in this case it is clear that in certain circumstance sqrt(x) can be less than p (eg: 15838 = 7919 * 2, where 7919 > sqrt(15838)), for primal testing the sqrt(n) bound is ok, however its not suitable for the upper bound in this problem.

cp9876 wrote:

This is much more efficient than testing the remaining 15,703 factors.

Ian Uy wrote:

It is said that the most complex structures built by mankind are software systems.

Ian Uy wrote:

Is it possible to get the rightmost NON-ZERO digit of a factorial without calculating for it?

static int fac_last_digit(int x)
{
    int res = x;
    int mod = 10;
    while (x > 1)
    {
        if ((res * (x - 1)) % mod == 0) mod *= 10;
        res = (res * (--x)) % mod;
    }
    return (res / (mod / 10));
}

private int rightmostNonzeroInFactorial(int n) {
	int result = 1;
	// factor ending on 1
	// no change
	// factor ending on 2
	int count2 = (n+8) / 10;
	// factor ending on 3
	int count3 = (n + 7) / 10;
	// factor ending on 4
	int count4 = (n + 6) / 10;
	// factor ending on 5
	int count5 = (n + 5) / 10;
	// factor ending on 6
	int count6 = (n + 4) / 10;
	// factor ending on 7
	int count7 = (n + 3) / 10;
	// factor ending on 8
	int count8 = (n + 2) / 10;
	// factor ending on 9
	int count9 = (n + 1) / 10;
	// factor ending on 0
	int count10 = (n + 0) / 10;
	count5 += count10;
	if (count5 != 0) {
		result = (result * rightmostNonzeroInFactorial(count5)) % 10;
		count2 -= count5;
	}
	count2 += 2 * count4;	// 4 = 2*2
	count2 += 3 * count8;	// 8 = 2*2*2
	count2 += 4 * count6;	// 16 = 2*2*2*2

	count3 += 2 * count9;	// 9 = 3*3;
	count3 += 3 * count7;	// 27 = 3*3*3

	int[] fact3 = new int[] { 1, 3, 9, 7 };	// 3^5 ends on 3
	result = (result * fact3[count3 % fact3.Length]) % 10;

	int[] fact2 = new int[] { 1, 2, 4, 8 };	// 2^5 ends on 2
	int factor2=fact2[count2 % fact2.Length];
	if (factor2 == 1 && count2 != 0) factor2 = 6;	// 2^4 = 16
	result = (result * factor2) % 10;

	return result;
}

Luc Pattyn [Forum Guidelines] [My Articles]

---

Voting for dummies? No thanks.

---

Luc Pattyn wrote:

countN tells me how many factors of n! end on digit N

count5 += count10;	
if (count5 != 0) 
   {
   result = (result * rightmostNonzeroInFactorial(count5)) % 10;
   count2 -= count5;
   }

if (count5 != 0) 
   {
   result = (result * rightmostNonzeroInFactorial(count5)) % 10;
   count2 -= count5;
   }
if (count10 != 0) 
   {
   result = (result * rightmostNonzeroInFactorial(count10)) % 10;
   }