11476 - Factorizing Large Integers

[octaviang]

I have an idea. What if you try recursivity? Just like in math, when we use recurrent functions, we can apply the formulas also here:
We' ll use n!=(n-1)!*n, for any natural number n >=1.

#include <iostream.h>
int factorial(n)
{
if(n==1)
return 1;
else return factorial(n-1) * n;
}
main()
{
cout<<"n=";cin>>n;
factorial(n);
}

Let' s make a debug. (I won' t run for big natural numbers the program now , but you' ll see the idea)
Let the natural number n be 5. The computer reads it, then the factorial(5) function is called. The variable answer takes the value of what this function return. And this will be:
return factorial(5-1)*5 = factorial(4)*5, which brings us to calling again the factorial function. Only this time, n=4. We check again if n=1, we see n=4 then we return factorial(4-1)*4 = . We can' t return a number so far, because we' re in the middle of a recurrent process: factorial(3)*4*5. What we can do is calling the factorial(3). This brings us to return factorial(2)*3. And multiplied with the previous result we get (factorial(2)*3*4*5 -factorial(2) equals factorial(1)*2. So until now, based on the previous calculus, we have factorial(1)*2*3*4*5 Now n==1 => we stop the recurrent calculus and we return the value of factorial(1), which is 1, plus the other factors: 2*3*4*5*6. Now, we have the entire result.

The complexity in time (O(n)) of this method is improved.

[Sedefcho]

[deleted]

[dibery]

An input generator.

Code: Select all

#include<bits/stdc++.h>
using namespace std;

long long r()
{
	char s[ 16 ] = { 0 };
	for( int i = 0, len = rand() % 15 + 1; i < len; ++i )
		s[ i ] = rand() % 10 + '0';
	long long a = max( 2ll, strtoll( s, 0, 10 ) );
	return a;
}

int main()
{
	srand( time( NULL ) );
	puts( "1000" );
	for( int i = 0; i < 1000; ++i )
		printf( "%lld\n", r() );
}