Spoiler alert: This post contains spoilers for Project Euler.
Problem 3
Largest Prime Factor of the number 600,851,475,143
JS Solution
This problem has a well known solution of using the prime factorization method. Some schools will teach this to kids around the same time they learn about primes and/or least/greatest common denominator. It's easy to forget this method as you get older but, it's not terribly complicated.
The idea is to continually divide a number by the next smallest prime number candidate (odd number). You also don't need to test factors that are larger than the square root of the remaining number. This keeps the search space small enough to make this process feasible.
Example:
let ceiling = 55
-
55 is not divisible by 2, try 3 next
-
55 is not divisible by 3, try 5 next
-
55 / 5 = 11
-
11 is not divisible by 5, and 5 > sqrt(11) so we don't need to try any more numbers. That means 11 is the greatest prime factor of 55.