Project Euler/3

Problem 3 on Project Euler: Problem 5 on Project Euler: https://projecteuler.net/problem=3

Solution: https://git.charlesreid1.com/cs/euler/src/master/003

In this problem we are finding the largest prime factor of an integer.

Approach

This task is similar to finding the complete prime factorization, except in special cases. For example, 1118125 = 5^4 * 1789 - if we start our search for prime factors at 2, we'll get stuck dividing out all the 5s and get to the largest prime factor (1789) last.

Rather, we should start at the integer itself, and work our way down. The worse cases are:

1. The number itself is prime, so we should check the number itself 2. The number is a product of 2 and a prime number (maximizes size of other prime number).

So we should check if our number is prime, and start counting from halfway to the number, counting down to 2, and checking for perfect divisors. In the case of finding the largest prime factor, we quit when we find the first prime factor (the largest). In the case of finding the prime factorization of a number, we continue until we reach 1 (like Euclidean algorithm).

Generalization

The generalization of what we're doing here is to pull out prime factors in a particular order - useful if there are a very large number of factors in a number. This functionality can be added to an Euler Library for use in later problems.