DEV Community

Cover image for Project Euler Problem 3 Solved with Javascript
Jared
Jared

Posted on

3

Project Euler Problem 3 Solved with Javascript

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);
Enter fullscreen mode Exit fullscreen mode

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

Image of Datadog

The Essential Toolkit for Front-end Developers

Take a user-centric approach to front-end monitoring that evolves alongside increasingly complex frameworks and single-page applications.

Get The Kit

Top comments (0)

Image of Datadog

Create and maintain end-to-end frontend tests

Learn best practices on creating frontend tests, testing on-premise apps, integrating tests into your CI/CD pipeline, and using Datadog’s testing tunnel.

Download The Guide

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay