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

-
that is so much code... –  Grady Player Apr 11 at 20:26
what do you know about all of the factors you are testing above the square root of n? –  Grady Player Apr 11 at 20:28
This code is very inefficient. Try it on 600851475177 instead and it takes forever. –  SpiderPig Apr 12 at 1:36
@SpiderPig - I am sorry but I am quite new to programming. Can you please give me a hint for a faster algorithm ? :) –  user2040026 Apr 12 at 3:23
@GradyPlayer - I don't get it. –  user2040026 Apr 12 at 3:27

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.

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


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.

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.

-
Excellent answer. Thank you so much. :) –  user2040026 Apr 11 at 14:24
Great answer, but this code would be greatly simplified by not using a list. You seek the biggest factor that is prime. Either work your way up from 2, or down from sqrt n, but each time you find a factor, check if it's prime. I like the going down method myself. The first one you find that is prime, stop. –  Dov Apr 24 at 4:27
@Dov: My gut feeling tells me that this approach is slower, as you have to test for primeness very often, which is a very costly operation. It could be sped up by having a precomputed list of primes but then you would need a big one that includes the possible factors of the number you want to test. Reducing the number by division significantly improves the runtime of the more common case of non prime numbers (if you see each number as equally likely). –  Nobody Apr 24 at 8:35

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

How high do we need consider? The largest candidate would be $\left\lceil\sqrt{n}\right\rceil$.

What algorithm could we use? A good method to build a list of many prime numbers is the Sieve of Eratosthenes. That would require $\left\lceil\sqrt{n}\right\rceil$ bits of memory, or 70 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?

-
That's one hell of an answer. Awesome. :) –  user2040026 Apr 26 at 9:44
I should have started earlier with writing about it. +1 one for the reference. Let me give one more point that I would have written about (which also is implicitly contained in your reasoning): Starting from the lower primes has on average the probability to find factors of a random number. Every second number has two as a factor, every third 3 and so on. This indicates that the probability distribution of finding a factor clearly leans towards the lower end. –  Nobody Apr 28 at 8:50
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;

-
"Kill the brackets" is against many guidelines (most?). Many reviews here would have said instead "add brackets" in case there weren't already. –  Morwenn Apr 11 at 13:46
@Morwenn it an opinion based and there is no definitive answer on that, however I highly recommend it, as it clears up the code from pointless fluff and allows you to more simply see what is going on. Most will agree that you shouldn't mix these two approaches within the context of a single if-else, so not to have brackets for half and not for the second, in this particular case, the brackets were serving one purpose... to get in the way of anyone trying to read the code. –  BenVlodgi Apr 11 at 13:50
On the other hand, you can later add statements to the body of your if or else without risking to forget the braces, which is safer. –  Morwenn Apr 11 at 13:54
Great answer. Thanks a lot. :) –  user2040026 Apr 11 at 14:25

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

-
Thanks for the Wiki references. :) –  user2040026 Apr 11 at 14:26
And I had this major confusion with whether to use one lettered variable names or not. You cleared it up. –  user2040026 Apr 11 at 14:35

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

-
Could you explain what you mean in your naming paragraph? I feel the getLargestPrimeFactor does what it is supposed to do. Also, it looks as if customization points are a bit overkill for some simple arithmetic calculations. What would you customize in this special instance (could you give a code example)? –  Nobody Apr 11 at 13:36
@Nobody : My point with the "naming" part is that if one function says it will do something, then it must do it. If someone needs a getTheJobDone function, then providing doFirstPart, doSecondPart and doThirdPart instead, needing the caller to call the three functions one after the other is perhaps misguided... About the customization, yes, it is overkill, but this is how I understood the question: In a more general problem, this is one way to provide customization. I'll think about a code example as soon as I am able to. –  paercebal Apr 11 at 13:42
If these functions are there to solve subproblems, then why not? The getLargestPrimeFactor function does to the user exactly what is needed: It returns the largest prime factor of a number. If you mean computePrimeFactors then I would be on your side :) This one should actually call computeFactors inside and only get the number as input. –  Nobody Apr 11 at 13:46

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.

-

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.

-
Thank you so much for your answer. It is very helpful. And I did the optimizations like returning false when number is evenly divisible by another in the loop and square root of n limit. And I thought about checking even divisibility first and then if it passes the test then proceeding further. But I was not sure whether its good practice or not. Thanks for clearing that up. And I implemented the sieve but the deletion of the elements from the list seems expensive. And I can't find a way to learn recursion properly. So I am stuck there. Thanks again. –  user2040026 Apr 24 at 5:28
WHen they teach the sieve, they show all the numbers being struck out, but you have to think out of the box. Why create numbers in a list and then get rid of them? Just don't put them in the list in the first place! Post a new question if you don't understand. You should definitely write a sieve if you're going to keep solving project Euler problems, you will need it! –  Dov Apr 24 at 5:30
I was thinking about it. Obviously I will not strike out numbers from list. But I didn't try hard. I will try it and if I write the code, I will make a post for reviews. :) –  user2040026 Apr 24 at 5:37
As long as you're interested in efficiency, pre-allocate the space you need. You know approximately how many prime numbers you want to store, so reserve that much space in the vector. Then fill it. Even faster than sieve is not even testing numbers, so try to skip multiples. Standard trick is to do multiples of 6+/-1, ie 5 and 7, 11 and 13, 17 and 19. Because anything that is divisible by 6 is obviously not prime, nor is anything that is 6 mod 2, 3, or 4. T –  Dov Apr 25 at 2:06