Largest prime factor – Project Euler Problem 3

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

now jump directly to iteration Number 71

i=71

600851475143%71=0 is true so

cursor will move to next line which is

num=num/i  means

num = 600851475143/71 which makes

num= 8462696833;

i=72

next iteration will be

if(8462696833%72 =0)

and so on

Final result:

Final result of this problem is 6857.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s