# Euler Problem 3

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

What is the largest prime factor of the number 600851475143 ?

There are probably a couple ways of tackling this one. The first one that comes to mind is to create a loop to the square root of the large number, test each to see if it’s a prime, then test each prime as a divisor and look for a zero remainder. Not elegant, but it works.

public class Euler3
{
public static void main(String[] args)
{
System.out.print(“Problem 3:\n”);
Euler3 e = new Euler3();
System.out.print(“Largest Prime Factor = ” + e.Problem3()+ “\n”);
}

public String Problem3 ()
{
long huge = 600851475143L;
long biggest = 0;
for (long i = 2; i <= Math.sqrt (huge); i++ )
{
if (isPrime(i) == true )
{
if (huge % i == 0)
{
biggest = i;
System.out.print(“Tested: ” + i +”\n”);
}
}
}
return String.valueOf(biggest);
}

public boolean isPrime (long num)
{
boolean prime = true;
int limit = (int) Math.sqrt (num);
for (int i = 2; i <= limit; i++ )
{
if ( num % i == 0 )
{
prime = false;
break;
}
}
return prime;
}
}