Project Euler #3 - largest prime factor

Question

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:

1. I called a single function from main() that gives me the result.

2. Now that function calls other functions from itself rather than in main().

3. 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.

Answer 1

Let me start off by general reviewing and end with your specific question:

Documentation

It is good that you thought about documenting with comments. However, the ones you made can be improved.

Function comments document the function interface and as such should be located where the interface is declared (so at the beginning of your file).

They also should not document the obvious ("GET THE LARGEST PRIME FACTOR" for getLargestPrimeFactor) or irrelevant ("my magic").

They should state pre- and postconditions of the function and what the function does (if there is more to it than the function's name).

Think about adopting the use of computer readable documentation systems like doxygen to let IDE's and other tools aid you with correct documentation.

Maximize constness

For example in vector<llint> computePrimeFactors(vector<llint>& factorList) you don't write to the factorList so it should really be defined as const vector<llint>& factorList to indicate that. This makes the code easier to reason about.

Readability

If it is possible try to use C++11 which gives some nice features that improve readability. For example this:

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

can become this in C++11:

for(auto const &i : factorList)
{
  //check whether each of the element is prime
  if(isPrime(i)) {
     prime.push_back(i);
  }
}

You can access the first and last element of most containers without using iterators by front() and back() so you could write:

return primeList.back();

instead of:

vector<llint>::iterator i = primeList.end() - 1;
return *i;

Efficiency

At first you calculate some of the divisors (in getFactors) of the number and store them in a list. Then you process this list and pick out the primes with isPrime (in getPrimeFactors) by trying to divide them by all numbers below them.

But actually you could have obtained all prime factors in the first function (getFactors) if you had divided as long as it was possible:

if(n % i == 0) {
     //if it does push it into the vector
     list.push_back(i);
     //remove this prime factor from the number
     while(n % i == 0)
         n /= i;
}

Thereby you would avoid the necessity to later check if the factors are prime.

Naming

Your function computePrimeFactors is misnamed. Actually it should be called something like filterPrimes because it gets a list of numbers and returns the primes inside this list. The better approach for this name would be to get the number as parameter and return the prime factors while internally calling computeFactors:

vector<llint> computePrimeFactors(llint n) {
   vector<llint> factors = computeFactors(n);
   vector<llint> primeFactors;
   // c++11!
   std::copy_if(factors.begin(), factors.end(),
                std::back_inserter(primeFactors), 
                &isPrime);
   return prime;
}

I have also replaced the copy code by a stdlib function, which reduces the risk of programming errors while (usually) increasing readability.

Your question

Finally I will answer your question: In general it is good to break up logic units into functions that define clear boundaries and give a name to the unit. As such you would even further reduce the main function by making it's body another function that gets called from main. This allows reuse of the code later on.

However, in your code it is unlikely to be needed again, so it is not necessary to do this. I would however state, that you should not put more into main.

Answer 2

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:

1. 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!

2. 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!

3. 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?

Answer 3

1. As far as the methods you've created and are calling I see no problem with (as per your doubts). Functions calling functions is a good thing. Functions should pull all of their own weight, calling other functions when necessary, the coder shouldn't have to call those functions beforehand and pass in the parameters, unless of course there is a situation where you (the coder) do at times need to specify specific running values.

2. Your main looks good, however as far as aesthetics of your code goes, I would add spaces between your operators and symbols...

   //this
   cout<<"The largest prime factor is : "<<prime<<endl;
   
   //becomes
   cout << "The largest prime factor is : " << prime << endl;
   

   This lack of spacing is in other parts of the code, but I'm not going to point out everywhere.

3. Aesthetically this block of code could be re-factored a few different ways.

   //Use one liners and no ugly brackets.
   if(list.size() == 2) 
      return *(primeList.end());
   else
       primeList = computePrimeFactors(list);
   
   //Take advantage of the fact that you don't need an else after a return.
   if(list.size() == 2) 
       return *(primeList.end());
   primeList = computePrimeFactors(list);
   

4. Use shortcut operators

   n /= i;
   

5. Don't do extra work. There are two things to change about the code below.

   if(count == 2) {
       return true;
   } else {
       return false;
   }
   

   Kill the brackets as I did earlier. (opinion, and optional)

   if(count == 2)
       return true;
   else 
       return false;
   

   Now that we can see this code clearly, we can realize what it is actually doing. count == 2 yields a Boolean value which is then passed to the special if function, which then asks if the Boolean passed in was true, if so.. then return true, else false (oversimplification of what is happening on the low level, but you get the gist) count == 2 is a Boolean, so instead of using that in an if... just return the Boolean you got from using that operator.

   return count == 2;
   

Answer 4

This is absolutely fine. By calling only one function in main and letting it handle what it has been asked for, you are achieving the concept of abstraction, leaving out the unnecessary crunchy-details and just saying what you want, which is the largest prime factor of a given number. The user of this method does not need to know anything about how it works internally.

Abstraction is one of the key concepts of OOP, and since you are programming in C++, you'll start to see the benefits of using such patterns soon, when you start to use classes that can grow out bigger and more complex than expected. Then, you'll need to use encapsulation, which is achieved through abstraction. So, the earlier your adopt this kind of pattern, the easier it will be in the future for you to resolve other issues like these.

Now, regarding your code: one thing that I'd definitely do is drop these /* magic stuff happens here */ comments, which do more harm than good. They do not explain anything and just yell that this code probably smells. Also, you should pay more attention to your one-character-name variables, like n, which does not mean much and is hard (actually impossible, depending on the size of your code) to find through CTRLF if needed.

If you have access to C++11, you could also take a peek on it's features to improve your code. For example, loops such as

for(vector<llint>:: iterator i=factorList.begin();
                               i<factorList.end();
                               i++) {}

could become ranged-for loops

for(auto i: factorList) {}

Answer 5

I know you already accepted an answer, but I think you asked the wrong question, so I will try to correct your other design mistakes.

As I mentioned briefly in a comment, you are using a list when you should be doing a greedy loop. It doesn't matter how well structured your code is, if your algorithm is wildly overcomplicated, your code is by definition harder to read than it needs to be.

So in a problem like this, your first concern should not be abstract object oriented concerns like coupling. You should be thinking about getting the algorithm right.

Let's take a look at your isPrime function. The comment should describe what it does. You could say "return true if the number is prime" which is fairly obvious, though not as useless as your current comment. But you could also describe how you are checking.

"Count how many factors are in the number. A prime has exactly 2"

That would at least explain your logic. But you should learn cleaner logic. This is the standard way:

bool isPrime(unsigned long long n) {
  for (unsigned long long i = 2; i < n; i++)
    if (n % i == 0)
      return false; // if it divides, it's not prime
  return true;
}

That's the first level of brute force checking. It happens to be shorter, simpler, and considerably faster than yours. Why count how many divisors there are? The first one you get (except 1 which is a waste) you know you have a composite.

If you want speed, you then have to start trading off some complexity for a faster answer. There is no point in dividing by 4, 6, 8. If your number divides by 2, it is not prime, and if it does not, then it's odd. So:

bool isPrime(unsigned long long n) {
  if (n > 2 && n % 2 == 0) // special case, check if the number is even
    return false;
  const unsigned long long lim = sqrt(n);
  for (unsigned long long i = 3; i <= lim; i+=2) // not even, so only divide by odd
    if (n % i == 0)
      return false; // if it divides, it's not prime
  return true;
}

This is much faster because you only go up to sqrt(n), not n, and do it by 2 to boot. For n= 10^12, that's the difference between 1 trillion iterations, and 500,000.

If you are going to use a list in this problem, then it should be because you are implementing Eratosthenes' sieve (look it up on Wikipedia or here).

As it stands, I would start at the square root of the number in question, working my way down. When I find a divisor, I check if it is prime. If it is bigger than the current maximum, store the number as maximum. If it is composite, break that one up and find its factors recursively. Because you have to keep splitting composites into primes, I would make a recursive function to do that, but there won't be any list, and you can stop splitting the moment your number is smaller than the maximum you found so far.

If I were you, I would make a set of better and better isprime functions, because if you are going to keep tackling problems from project Euler you will need them.

In the long run, all the advice you were given is pretty good. But on a problem like this, the best way to keep the code clean is to clean up your logic, not to use doxygen.

Answer 6

Naming

What's the name of your function? "getLargestPrimeFactor"? So it must do all the work to solve the problem.

More generally, you want to make your code easy to use, and, if the user doesn't care about how it is done, providing one function with a correct name to do all the work is a welcome sight.

Customization

1. In one hand, you must provide a robust, bug-resistant, easy way for the user to get the result (here, the largest prime factor).
2. In the other, you could want to provide a way for the users to call the functions as it suits them. This should be optional, and this can be done different ways, depending on the type of customization you want to provide.

your priority is to provide the first part: A user should be able to easy have the expected result, the same way starting your car is just turning the key (or pressing the button).

If you really want to provide customization, then you must think carefully about the kind of customization you can, and thus, common idioms will apply.

For example, one naive solution would be to provide one class with all customization points being virtual methods. The users can then override the method they want to customize, while leaving the others as is. This needs research to find the right solution to your specific problem.

Answer 7

I think it's actually a really good habit to call functions from within functions. This is a very important concept in Object-Oriented Programming. If you wrote this source code using OOP, you might structure it like this...

• Class Main
  • main()
• Class PrimeFactors
  • public getLargestPrimeFactor()
  • private computeFactors()
  • private computePrimeFactors()
  • private isPrime()

As you can see, in this class any method called from Main is declared as public, and any method only called from within the class is declared as private.

Structuring this program as a class instead of a series of functions makes it easy to re-use the code. It makes Class PrimeFactors like a library that you can easily include into any main that you want.

I agree with the others about commenting less. I was reading Clean Code by Robert C. Martin the other day, and he argues that comments should be minimal and pragmatic. Ideally you want to choose very succinct names for your variables and functions/methods, and you want to make as many chunks of code into functions/methods as possible. And what this does is it names everything, which helps to avoid you needing to make as many comments in the first place. I think you're already on the right track with this because you wrote multiple functions and you tried to give them all good names.