Problem 3: Largest Prime Factor
Today we're going to tackle Project Euler problem number 3! We are going to learn all about primes and factors. This problem is fairly straight-forward, so we shouldn't have to dig too deep into Wikipedia.
Problem Discussion
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the given number?
Video Version
If you like to watch rather than read, check out the video that accompanies this article. If not, keep reading!
Prime Number
First, let's figure out what a prime number is, in case you forgot...which I did.
a whole number greater than 1 that can not be made by multiplying other whole numbers
Some examples are: 2, 3, 5 and 7.
Prime Factor
Rather than try and explain it in my own words, i'll let mathisfun.com do the explaining.
A factor that is a prime number.
or
In other words: any of the prime numbers that can be multiplied to give the original number.
Example
The factors of 35 are: 1, 5, 7, 35. 35 is a composite of 7 and 5, therefore 7 is the highest prime number, making it the highest prime factor.
Solution
Now that we are armed with grade school math, let's solve this thing!
Steps
- Iterate over all factors
- Check factor is a prime number
- Return last factor.
Code
function largestPrimeFactor(number) {
// setup local state
let primesAndFactor = [];
// find all factors
// In order to maintain this property of unique prime factorizations, it is necessary that the number one, 1, be categorized as neither prime nor composite.
for (let factorIterator = 0; factorIterator <= number; factorIterator++) {
// check if factor
let isFactor = number % factorIterator == 0;
let isPrime = true;
if (isFactor) {
// see if factor is a prime
// a prime number has two factors, 1 and itself
for (let i = 2; i < factorIterator; i++) {
if (factorIterator % i == 0) {
isPrime = false;
continue;
}
}
}
// if so, push to primes list
if (isFactor && isPrime) {
primesAndFactor.push(factorIterator);
}
} // end for loop
// return last element of array
return primesAndFactor.pop();
}
largestPrimeFactor(13195);
Final Thoughts
In this challenge, we start getting into the need for algorithms. This is a brute force approach that requires two for loops, which isn't ideal. This works okay for now, but we will need something more powerful for the next set of problems, I'm sure.
If you want to see the rest of my solutions, check them out here:
Top comments (0)