11476 - Factorizing Large Integers

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

New poster
Posts: 1
Joined: Mon Feb 23, 2009 3:22 pm

Re: 11476 - Factorizing Large Integers

Post by 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)
return 1;
else return factorial(n-1) * n;

Let' s make a debug. (I won' t run for big natural numbers the program now :D , 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.
Octavian Ghergheli
Meditatii Matematica

A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 11476 - Factorizing Large Integers

Post by Sedefcho »


Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei

Re: 11476 - Factorizing Large Integers

Post by dibery »

An input generator.

Code: Select all

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() );
Life shouldn't be null.

Post Reply

Return to “Volume 114 (11400-11499)”