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
#include
using std::cout;
using std::endl;
using std::vector;
typedef long long int llint;

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

int main() {
   llint num = 600851475143;
   llint prime;
   cout 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::iterator i=primeList.begin(); i::iterator i = primeList.end() - 1;
   return *i;
}

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

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

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?

StackExchange Code Review Q#46906, answer score: 21