I was going through the Project Euler problem #3 and made a program to solve it. The problem is as follows:
The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?
My code is as follows:
#include<iostream>
#include<vector>
using std::cout;
using std::endl;
using std::vector;
typedef long long int llint;
vector<llint> computeFactors(llint);
vector<llint> computePrimeFactors(vector<llint>&);
llint getLargestPrimeFactor(const llint);
bool isPrime(const llint);
int main() {
llint num = 600851475143;
llint prime;
cout<<"The number to factorize is : "<<num<<endl;
//call the function getLargestPrimeFactor to get the factor
prime = getLargestPrimeFactor(num);
cout<<"The largest prime factor is : "<<prime<<endl;
return 0;
}
//////////////////////////////////////////////////////////////
////////// GET THE LARGEST PRIME FACTOR BY MAGIC /////////////
//////////////////////////////////////////////////////////////
llint getLargestPrimeFactor(const llint n) {
vector<llint> list, primeList;
list = computeFactors(n);
//if n itself is prime then return n;
if(list.size()==2) {
return *(primeList.end());
} else {
primeList = computePrimeFactors(list);
}
for(vector<llint>::iterator i=primeList.begin(); i<primeList.end(); i++) {
cout<<*i<<endl;
}
vector<llint>::iterator i = primeList.end() - 1;
return *i;
}
//////////////////////////////////////////////////////////////
/////////// GET THE FACTORS /////////////////////////////////
//////////////////////////////////////////////////////////////
vector<llint> computeFactors(llint n) {
vector<llint> list;
//iterate through every number in the range
for(llint i=1; i<=n; i++) {
//find out whether any of the number divides n
if(n%i==0) {
//if it does push it into the vector
list.push_back(i);
n=n/i;
}
}
return list;
}
//////////////////////////////////////////////////////////////
/////////// GET THE PRIME FACTORS ////////////////////////////
//////////////////////////////////////////////////////////////
vector<llint> computePrimeFactors(vector<llint>& factorList) {
vector<llint> prime;
//iterate through every number in the vector
for(vector<llint>:: iterator i=factorList.begin();
i<factorList.end();
i++)
{
//check whether each of the element is prime
if(isPrime(*i)) {
prime.push_back(*i);
}
}
return prime;
}
//////////////////////////////////////////////////////////////
/////////// WHETHER A PRIME NUMBER ///////////////////////////
//////////////////////////////////////////////////////////////
bool isPrime(const llint n) {
int count = 0;
for(llint i=1; i<=n; i++) {
if(n%i==0) {
count++;
}
}
if(count == 2) {
return true;
} else {
return false;
}
}
My doubts start from here:
I called a single function from
main()
that gives me the result.Now that function calls other functions from itself rather than in
main()
.Those sub-functions call other functions to achieve the task.
So now while designing the program, I just had to think about a single function that gave me the result. Now I decompose the function into different parts.
So when I call the getLargestPrimeFactor()
, others are implicitly called.
But what I could have done is that I could have called each function explicitly in main()
.
Is there a difference in between the two approaches ? Does it really matter ? In what cases thinking like this can be harmful ? I have studied a bit about cohesion and coupling. I just want to get the habits right from the beginning.