Project Euler/3: Difference between revisions
From charlesreid1
(Created page with "Finding the largest prime factor of a given integer: This task is similar to finding the complete prime factorization, except in special cases. For example, 1118125 = 5^4 * 1...") |
No edit summary |
||
| Line 9: | Line 9: | ||
So we should check if our number is prime, and start counting from halfway to the number down to 2, 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). | So we should check if our number is prime, and start counting from halfway to the number down to 2, 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). | ||
{{ProjectEulerFlag}} | |||
[[Category:Math]] | |||
[[Category:Primes]] | |||
[[Category:Prime Numbers]] | |||
[[Category:Factoring]] | |||
Revision as of 20:57, 15 June 2017
Finding the largest prime factor of a given 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 down to 2, 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).
