Project Euler : Problem 3 - Largest prime factor

Problem Statement : Largest prime factor

Problem 3 : The prime factors of $13195$ are $5, \ 7, \ 13$ and $29$. What is the largest prime factor of the number $600851475143$ ?

Concept and Theory

The main idea behind this problem is to understand the basic factoring concept, i.e “any number, $N$, can have at-most one prime factor bigger than its $\sqrt{N}$, unless the number itself is prime”. Just like sieving in Sieve of Eratosthenes we do our computations.

• Since $2$ is the only special case, only even prime number, we will handle its case separately and keep updating our $currentLargestFactor$.
• After handling $2$’s special case, $currentLargestFactor = 3$ and we update it in increment of $2$ as we only care about odd numbers(because they are the only possible solution).
• As a last step, if after looping over $\sqrt{N}$ we are still left with some number we will simply make that number our answer. Why ? Because that will be the only one prime bigger than $\sqrt{N}$.

Code

/**
 * A function to calculate the largest prime factor of given number
 *
 * @param num
 *            : given number
 * @return largest prime factor of given number
 */
public static long largestPrimeFactor(long num) {

  long searchingRangeMaxNum = (long) Math.sqrt(num);
  long currentLargestFactor = 2;
  long largestFactor = 1;

  if (num % currentLargestFactor == 0) {
    largestFactor = currentLargestFactor;
    num /= currentLargestFactor;
    while (num % currentLargestFactor == 0) {
      num /= currentLargestFactor;
    }
  }

  if (num == 1) {
    return largestFactor;
  }

  currentLargestFactor = 3;

  while (currentLargestFactor <= searchingRangeMaxNum) {
    if (num % currentLargestFactor == 0) {
      while (num % currentLargestFactor == 0) {
        num = num / currentLargestFactor;
      }
      largestFactor = currentLargestFactor;
    }
    currentLargestFactor += 2;
  }
  if (num > 1) {
    largestFactor = num;
  }
  return largestFactor;
}

Test Your Skills

Wanna try a harder version of the above problem ? Check this HackerRank problem.

Solution

The solution will remain same as above method $largestPrimeFactor$, you just need to call it for each test case.

References and Further Readings

• ProjectEuler