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

1. Iterate over all factors
2. Check factor is a prime number
3. 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:

Resources

Prime Factor