Problem 3

Problem Statement

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Approach

Computing the largest prime factor of an arbitrarily large number $n$ is a somewhat daunting task at first. One elementary way to approach the problem is to find all prime numbers less than or equal to $\sqrt{n}$, then working our way down from the biggest prime below $\sqrt{n}$, check if $n \mod P_i == 0$ where $P_i$ represents the ith prime in the list. Of course, we know that this method is always verifiably correct; by finding the biggest possible prime and then working backwards, we know that as soon as we hit the first prime that is evenly divisible we will have found the biggest prime factor. However, this method is not particularly quick. Can you imagine having to find all primes $P \leq \sqrt{600851475143}$? This would be computationally intensive, and as we'll soon see, is not necessary to solve this problem. Instead, we can rely on a variation on Fermat's approach to factoring. Let's choose the number $56$ as our starting number to factor. Visually, we know that the prime factorization of $56 = 2^3 * 7$. One can note that by finding the multiplicity of each prime factor, we will be able to get the largest prime factor. If we start with the smallest prime number, 2, we can figure out how many times $2$ factors into $n$ by evaluating $n /= 2$ as long as $n \mod 2 == 0$. As soon as $n \mod 2 \neq 0$, we can increment to the next value, 3. 3 happens to also be prime, and we repeat our procedure. Now, what happens if we hit 4? Well, since we already know that $n \mod 2 \neq 0$, we know $n \mod 4 \neq 0$. More generally, we know that for any composite number $i$ that we encounter where $2 < i < \sqrt{n}$, $n \mod i \neq 0$. Thus, this method gives us that we are always going to find prime factors. Of these prime factors, we want to store the biggest one, so we update the value of our biggest prime factor every time $n \mod i == 0$ in the while loop. Finally, we can just return the answer.

C++ implementation

```
````#include <stdc++.h> `

`using namespace std;`

`long long int largestPrimeFactor(long long int n) {`

` long long int res = 0;`

` long long int smalln = ceil(sqrt(n));`

` while(n % 2 == 0) {`

` res = 2;`

` n /= 2;`

` }`

` for(int i = 3; i < smalln; i+=2) {`

` while (n % i == 0) {`

` res = i;`

` n /= i;`

` }`

` }`

` return res;`

`}`

`int main() {`

` cout << largestPrimeFactor(600851475143) << endl;`

` return 0;`

`}`

You can also download the source code for this problem here and compile it on your local machine.

Further Analysis

There are definitely some things that are happening programming-wise that are important to pick up on and carry through to the rest of the Project Euler problems. The most important thing is probably the introduction of a new data type for storing integers that I've called `long long int`

. This data type is useful because it is able to represent $2^{64}$ different numbers, whereas the regular 32-bit integer in C++ can only represent $2^32$ integers. If you are having trouble seeing why this is true, think about how many bits there are in a regular int (32) versus a long long int (64). Since each bit can either be turned "on" or "off" by setting the bit value to 1 or 0, we know that there are 2^{n} different numbers that can be represented with an $n$-bit integer. Also, since we need to be able to represent both negative and positive integers, the maximum integer value you can represent in an int (called INT_MAX) is $2^{31}-1$. We lose one power of two becuase we use the top bit to indicate whether the sign of the number is negative or positive (often called the sign bit), and then we subtract one value because the maximum positive integer you can represent is always one less than the number of non-negative numbers you can represent (since zero needs to be represented). If you are ever solving a Project Euler question and you notice that your number are overflowing / truncating in your current data type representation, try switching from `int`

to `long long int`

.