Largest prime factor

The Largest prime factor is a very simple concept. Let’s break it down:

  • Every number has many different factors.
  • Factors are numbers that completely divide a particular number to get zero as a remainder.
  • For example, if we look at the number 6, it has four factors: 1,2,3,6. However, of these factors, 2 and 3 are prime numbers. As 3 is greater than 2, 3 is said to be the largest prime factor of number 6.
svg viewer

Code

Explanation: For any number, we must first find out all the factors associated with it. For example, if we look at the number 123, we can see that it has two factors: 41 and ,3. In the code, we run a loop from number/2 to 2.(If we run the reverse loop we will find the largest factor first without the hassle to check the smaller ones first). In this case, the loop will run from 61 to 2. Now, we will check if this i is a factor of the given number. If it is a factor then we will check each factor is also a prime number. We have defined a helper function in the code to check if a number is prime or not – we call this function on every factor. If the number is a factor and also a prime, we add it to the maintained list of factors. At last, we find out the maximum number from the list to obtain the largest prime factor.

Free Resources

Copyright ©2024 Educative, Inc. All rights reserved