Thursday, May 25, 2006

Another interesting program!

At last, i found something to write in this blog!

Somedays back, i was just fiddling with the linux shell which has umpteen number of commands( Of which i know only a few! Chee chee! ). Was just goin thru one command 'factor' and found it a bit interesting!

Since then, was tryin to write it in my way! It may not be efficient, but i've got the satisfaction of tryin that interesting one!

All factor does is print all the prime factors of the number passed.

If you're interested in writing one, dont go thru right now, try writing it once and get the satisfaction.

Here goes my implementation!

#include < iostream &gt
#include < iomanip &gt
#include < cmath &gt
#include < climits &gt

using namespace std;

unsigned long long isPrime( unsigned long long number )
{
unsigned long long rootOfNumber = static_cast < unsigned long long &gt ( sqrt( number ) );

if( !( rootOfNumber % 2 ) ) rootOfNumber += 1;

for( unsigned long long i = 3; i <= rootOfNumber; i++ ) if( !( number % i ) ) return i; return 0; } void printPrimeFactors( unsigned long long number ) { unsigned long long result = 0, resultPair = 0; result = isPrime( number ); if( !result ) cout << ' ' << resultpair =" number" length =" strlen(" i =" 0;" result =" 0;" initialzeros =" true;"> 19 && ( strcmp( number, "18446744073709551615" ) > 0 ) )
{
cerr << " Error : Bejaan doddadaythu! Hogolo! " << i =" 0;" initialzeros =" false," digit =" number[">>= 1;
}
if( number > 1 )
printPrimeFactors( number );
else if( number >= 0 )
cout <<>> number;
primeFactors( number );
}
else
{
for( int i = 1; i < argc; i++ )
{
if( argv[ i ][ 0 ] != '-' )
{
number = stringToUnsignedLongLong( argv[ i ] );
primeFactors( number );
}
else
cout << " No negative values please!! " << endl;
}
}
cout << endl;

return 0;
}

Writing this in my stupidly busy schedule took me 2 weeks outa which i've spent 3 hours effectively to write this!

Explaination goes as follows.

You need, iostream, iomanip to print into the console. cmath for sqrt and limits for limit of long long!

If some of you dont know that there is a modifier for int called long long, its a 64 bit number introduced with the std c99 C standard. This program finds prime factors for all the numbers falling in that range.

isPrime function checks whether the number passed is a prime number or not! This is a customised function which finds prime numbers only in this program. Try using this function outside, it'll fail coz it doesn't handle even numbers. ( Wanna know how?? I'm not passing any even number to this function! )

What happens in that function is it finds the square root of the number which is supposed to be decided as prime or not! We loop in the interval [3,sqrt(number)]. If( sqrt(number) is even, we add 1 so that its odd!
If you've some math background in Primes, you'll know that, if you dont find any number in [2,sqrt(number)], which divides the number, its a prime. This is what the function checks for. If it finds one, it just returns the factor, else, it returns 0.

printPrimeFactors is a recursive function that calls itself on the factors of the number. It tries to fins whether the number is prime, if so prints it and exits ( this is the exit condition of recursion ). Else, it gets the factor, finds its pair, and calls itself on these numbers finally printing the prime factors recursively! ( Try an example, you'll understand it better! ).

stringToUnsignedLongLong is a function written as i found atoll not fillin my needs at this moment! Had got some time and thought of not wasting time to debug on these things. This function just returns the unsigned long long of the string it gets as the argument. It just parses the string and adds on multiplying the result with 10. Simple logic!

PrimeFactors was just a dummy function written coz that part of code was called twice in the driver ( main ). You can omit it! It just checks for boundary condition and passes the correct argument for printPrimeFactors().

Main is a driver program demonstrating the function.

Still have doubts???????????

Contact me!

Thats it for now! Catch ya soon with somethin more interesting!

1 Comments:

Blogger Sandesh said...

Finding some difficulty publishing < and > symbols! Will come out with a solution for that asap!

5:37 AM  

Post a Comment

<< Home