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

How to Diagram Your Cloud Architecture

Cloud architecture diagrams provide critical visibility into the resources in your environment and how they’re connected. In our latest eBook, AWS Solution Architects Jason Mimick and James Wenzel walk through best practices on how to build effective and professional diagrams.

Download the Free eBook

Top comments (0)

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

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

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

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay