Euler Problem: Solution of Problem-3 in C++

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

Published by

Sreejith

A strong believer of: 1. Knowledge is power 2. Progress comes from proper application of knowledge 3. Reverent attains wisdom 4. For one's own salvation, and for the welfare of the world

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s