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;
    }
}

 

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 )

Connecting to %s