Problem 3 on Project Euler: Problem 5 on Project Euler: https://projecteuler.net/problem=3
In this problem we are finding the largest prime factor of an integer.
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).
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.
Project Eulerproject euler notes
Round 1: Problems 1-20
Round 2: Problems 50-70
Round 3: Problems 100-110
Round 4: Problems 500-510
Round 5: Problems 150-160
Round 6: Problems 250-260
Round 7: Problems 170-180Flags · Template:ProjectEulerFlag · e