Hey there! In this post you will find the solution of third problem of Project Euler.You can find solutions of first two problems here

Problem Statement:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Solution:

public class LargestPrimeFactor{
public static void main(String args[]){
long num=600851475143l;
int i=2;
while(num>1){
if(num%i==0)
numb=num/i;
i++;
}
System.out.println(--i);
}
}

I have created this logic using very generic approach, this code can be used to find largest prime factor of any number, you just need to assign that value to ‘num’.If you want to make it more generic/user-friendly you can use command-line input or can also use value from a file but the logic to calculate largest prime factor would remain same.

Moving to the explanation of above mentioned code we first need to understand what is Prime factor. Prime Factor and Prime factorization can help us understand it.

Now as we know what is prime factor we can easily calculate largest Prime factor.

There are two variables ‘num’ and ‘i’.

‘num’ holds the actual number whose largest prime factor we have been asked to find and ‘i’ is used in loop.

num=600851475143l

Starting loop from 2, we check whenever ‘num’ is divisible by any number, giving remainder 0

if(num%i==0)

we will divide ‘num’ with that number keeping result in ‘num’

num=num/i;

value of i will be incremented by 1

i++;

Again system check for the remainder and if the check is true ‘num’ will be divided by that number until ‘num’ will be less than 1.

as the result ‘i’ will have desired value but since we increment ‘i’ at the end of loop, ‘i’ will be incremented by 1 so we have to minus 1 from ‘i’.

Lets dry run it,

First Iteration:

num=600851475143;

i=2

600851475143>2 : which of course is true

600851475143%2 =0 is false so

inner step num=num/i; will be skipped and loop forwards by 1 which means i=3

till i=70 loop produces same result as none of the numbers uptil 71 is a multiple of 600851475143