Project Euler/3: Difference between revisions
From charlesreid1
No edit summary |
m (Replacing charlesreid1.com:3000 with git.charlesreid1.com) |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
Problem 3 on Project Euler: Problem 5 on Project Euler: https://projecteuler.net/problem=3 | Problem 3 on Project Euler: Problem 5 on Project Euler: https://projecteuler.net/problem=3 | ||
Solution: https://git.charlesreid1.com/cs/euler/src/master/003 | |||
In this problem we are finding the largest prime factor of an integer. | |||
==Approach== | |||
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. | 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. | ||
| Line 11: | Line 14: | ||
2. The number is a product of 2 and a prime number (maximizes size of other prime number). | 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). | 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). | ||
==Generalization== | |||
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. | |||
{{ProjectEulerFlag}} | {{ProjectEulerFlag}} | ||
Latest revision as of 03:47, 9 October 2019
Problem 3 on Project Euler: Problem 5 on Project Euler: https://projecteuler.net/problem=3
Solution: https://git.charlesreid1.com/cs/euler/src/master/003
In this problem we are finding the largest prime factor of an integer.
Approach
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).
Generalization
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.
