#Skip to menu

Greatest prime factor

First read the problem description.

First we make sure \(n\) is odd. Then starting with \(p_1 = 3\) we remove from \(n\) all \(p_i\) multiplies. Doing the same with \(p_2 = 5\), \(p_3 = 7\), \(p_4 = 9\), etc. Since a composite number \(c\) is composed of two or more primes lesser than \(c\), we know that if \(p_i\) is composite it will not divide \(n\) because all \(c\)’s factors have already been removed from \(n\). So if \(p_i\) divides \(n\) it means it’s prime. We proceed until \(n = 1\), in which case we know that \(p_i\) is the greatest prime factor.

Source code of the solution(s):