Problem 3 of Project Euler is a computational beast. Nothing more. The problem, as stated on the website is:

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

What is the largest prime factor of the number 600851475143 ?

## General Algorithm

Before we start, we have to take a few things into account:

- 600851475143 is an insanely large number. Languages like C/C++ have no native support for big integers. Luckily for us, we can store this in a
**long long unsigned int**. - While testing for primes, the following information must be kept in mind:

- While the definition of prime numbers is known to most, the second point is rather important. It implies that we need only to check for factors of a number till √n and not till n.

The algorithm is as follows:

- Initialise
**const long long unsigned int**n = 600851475143. - Iterate
*i*through every integer from*√n*to 1. - If
*i*perfectly divides*n*, then:

- If
*i*is prime then the highest factor is*i* - If
*i*is not prime, then check if*n/i*is prime. If*n/i*is prime, then*n/i*is the highest factor. - If neither
*i*nor*n/i*is prime, then continue through the loop

- Break the loop.

Advertisements