Problem 3: Largest prime factor

Algorthim:

This was a good chance to practice some number theory though the problem is much simpler looking back as I write this.

Fermat's Factoring theorem assumes that the number we want to factor is an odd number and since we are given the number we want to factor, this is not big of a deal. However, we can easily divide by two until the number "runs out" of two's.

Incorporating the Fermat's theorem is enough to do. It's a fairly easy algorthim and very intuitive to understand. One does not even have to understand it to solve this. There were three major steps in solving this problem

1. Get rid of any two's in the number. This is indicated using the variable "two" in the code
2. Apply Fermat's Factorization method.
   • Returns 'prime' if a factor is prime
   • Else, returns an array with two numbers that could be prime
3. Recursively apply Fermat's method to the remaining numbers that were outputs of Fermat's theorem. If the number is prime, store in an array. If not, apply Fermat again

The code ends when all the numbers in a stored array (called "res" in the code) is empty. The final step is just to count the number of occurence of each unique prime (but that wasn't necessary). Maximum prime is easy enough to find using max() function

Notice that this code can intake any valid positive integer!

Code: