Q) The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?
#include <algorithm> #include <iostream> #include <vector> #include <math.h> using namespace std; unsigned long largest_prime_factor_of ( unsigned long num ) { clog << "largest_prime_factor_of(" << num << ")" << endl; unsigned long largest_prime_divisor = -1; if ( num < 2 ) { return -1; } else if ( num >=2 && num<=3 ) { return num; } while ( num%static_cast<unsigned long>(2) == 0 ) { largest_prime_divisor = 2; cout << "/2" << endl; //cout << "num%static_cast(2) = " << num%static_cast(2) << " num/static_cast(2) = " << num/static_cast(2) << endl; num /= 2; } while ( num%3 == 0 ) { largest_prime_divisor = 3; cout << "/3" << endl; //cout << "num%static_cast(3) = " << num%static_cast(3) << " num/static_cast(3) = " << num/static_cast(3) << endl; num /= 3; } vector<unsigned long> prime_num_vector; prime_num_vector.push_back(static_cast<unsigned long>(3)); clog << "largest_prime_divisor(after checking till 3) = " << largest_prime_divisor << "and num = " << num << endl; unsigned long divisor = 3; bool divisor_is_prime; while ( (divisor+2) <= num ) { //cout << "."; divisor += 2; clog << "divisor = " << divisor << endl; divisor_is_prime=true; double sqrt_of_divisor = sqrt(divisor); clog << "sqrt_of_divisor = " << sqrt_of_divisor << endl; clog << "going inside for-loop" << endl; for( vector::iterator iter = prime_num_vector.begin(); iter != prime_num_vector.end(); iter++) { clog << "\t*iter = " << *iter << endl; if ( *iter > sqrt_of_divisor ) { clog << "\t*iter > sqrt_of_divisor" << endl; break; } if ( divisor % *iter == 0 ) { clog << "\tdivisor_is_prime = false" << endl; divisor_is_prime = false; break; } } if ( divisor_is_prime ) { clog << "divisor_is_prime (" << divisor << ")" << endl; prime_num_vector.push_back ( divisor ); while ( num % divisor == 0 ) { largest_prime_divisor = divisor; num /= divisor; cout << "largest_prime_divisor changed to " << largest_prime_divisor << " and num = " << num << endl; } } } clog << "returning " << largest_prime_divisor << endl; return largest_prime_divisor; } int main ( int argc, char *argv[] ) { unsigned long l = 600851475143 ; //unsigned long l = 12 ; cout << endl << "largest_prime_factor_of(l) = " << largest_prime_factor_of(l) << endl; }