Project Euler #3 - largest prime factor 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&lt;iostream&gt;
#include&lt;vector&gt;
using std::cout;
using std::endl;
using std::vector;
typedef long long int llint;

vector&lt;llint&gt; computeFactors(llint);
vector&lt;llint&gt; computePrimeFactors(vector&lt;llint&gt;&amp;);
llint getLargestPrimeFactor(const llint);
bool isPrime(const llint);

int main() {
   llint num = 600851475143;
   llint prime;
   cout&lt;&lt;"The number to factorize is : "&lt;&lt;num&lt;&lt;endl;
   //call the function getLargestPrimeFactor to get the factor
   prime = getLargestPrimeFactor(num);
   cout&lt;&lt;"The largest prime factor is : "&lt;&lt;prime&lt;&lt;endl;
   return 0;
}

//////////////////////////////////////////////////////////////
////////// GET THE LARGEST PRIME FACTOR BY MAGIC /////////////
//////////////////////////////////////////////////////////////

llint getLargestPrimeFactor(const llint n) {
   vector&lt;llint&gt; 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&lt;llint&gt;::iterator i=primeList.begin(); i&lt;primeList.end(); i++) {
      cout&lt;&lt;*i&lt;&lt;endl;
   }
   vector&lt;llint&gt;::iterator i = primeList.end() - 1;
   return *i;
}

//////////////////////////////////////////////////////////////
/////////// GET THE FACTORS  /////////////////////////////////
//////////////////////////////////////////////////////////////

vector&lt;llint&gt; computeFactors(llint n) {
   vector&lt;llint&gt; list;
   //iterate through every number in the range
   for(llint i=1; i&lt;=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&lt;llint&gt; computePrimeFactors(vector&lt;llint&gt;&amp; factorList) {
   vector&lt;llint&gt; prime;
   //iterate through every number in the vector
   for(vector&lt;llint&gt;:: iterator i=factorList.begin();
                               i&lt;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&lt;=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.
Algorithm

I think you've gotten distracted by focusing on the wrong aspect of the problem.

The challenge asks for the largest prime factor of n = 600851475143.  There are three approaches you might consider in tackling this challenge:


Construct the list of all relevant prime numbers, then take the largest one that is a factor of n.

How high do we need consider?  The largest candidate would be \$\frac{n}{3}\$.

What algorithm could we use?  A good method to build a list of many prime numbers is the Sieve of Eratosthenes.  That would require \$\frac{n}{3}\$ bits of memory, or 23 GiB. Even if you had a machine with that much memory, just initializing that much memory to zero would be too slow to be reasonable as a Project Euler solution.

Any other algorithm for building a list of primes would only be worse.

You didn't choose Door #1.  Good for you!
Test the largest candidate factors first.

Where would you start?  The largest candidate would be \$\left\lceil\sqrt{n}\right\rceil\$.  You can test odd candidates in descending order, stopping as soon as you find an answer that is prime.

How do you guarantee that the answer is prime?  You have to check for primality.  We've already ruled out the Sieve of Eratosthenes above, so you would have to use trial division or a fancier primality-testing algorithm.

How long would we expect this to take?  \$\left\lceil\sqrt{n}\right\rceil\$ is 775147.  We would have 387573 possible odd factors to test.  There's no telling where we'll find numbers that are actually factors of \$n\$.  Once we find a factor, we still have to verify whether it's prime.

Food for thought: what would you do if \$n\$ were even?

You didn't choose Door #2, even though some other users have advocated it.  Good for you!
Test the smallest candidate factors first.

Suppose that I asked you to find the largest prime factor of 10241.  How would you go about it?  Would you start at \$\left\lceil\sqrt{10241}\ \right\rceil\$, trying 103, 101, 99, 97, 95, …?

Chances are, you would prefer to do it the following way instead, and you could do it with just pencil and paper.  (It's also easy to implement as one function.)


10241 / 2 … no.
10241 / 3 … no.
10241 / 5 … no.
10241 / 7 = 1463
1463 / 7 = 209
209 / 7 … no.
209 / 9 … no.
209 / 11 = 19
19 / 11 … no.
19 / 13 … no.
19 / 15 … no.
19 / 17 = no.
19 / 19 = 1
done!


As you can see, the big win comes when you find that 10241 is divisible by 7 — you immediately reduce the search space by a factor of 7.  In just a few iterations, you've reduced the problem size from 10241 down to 209 — a much more manageable number.

Bonus question: in the example above, do we still need to test 19 for primality?  Why or why not?


As it turns out, strategy 3 also works well for Project Euler Problem 3.  In general, strategy 3 is a better bet than strategy 2, since prime numbers tend to be more densely clustered closer to 0.

You've chosen an algorithm that is similar to strategy 3, which is good.  However, it isn't the same solution.  Your computeFactors() function very closely mimics the algorithm illustrated for strategy 3, but with a subtle and crucial difference.  Can you spot it?