I'm trying Euler problem 3 on http://projecteuler.net/ for fun. I think I have a program that works (with very small numbers), but it takes too long. Can anyone give me some hints to improve speed?

/**
 * The prime factors of 13195 are 5, 7, 13 and 29.
 * What is the largest prime factor of the number 600851475143 ?
 * 
 * Start from 600851475143 and count backwards, looking for factors. Every time 
 * you get a factor, check to see if it is prime. The first prime factor starting
 * for the top is the largest prime factor.
 */
public class Euler3
{
    public static void main(String[] args)
    {
       Euler3 euler3 = new Euler3();
       euler3.getLargestPrimeFactor();
    }
    
    public void getLargestPrimeFactor()
    {
        long number = 26;
        boolean primeFactor = false;
        boolean factorFound = false;
        long originalNumber = number;
        long factor = 0;
        long index = originalNumber - 1;
        while (!primeFactor)
        {
            while (!factorFound && index > 1)
            {
                if ( originalNumber % index == 0 )
                {
                    factor = index;
                    factorFound = true;
                
                }
                index--;
            }
            if (isPrime(factor) == true)
                primeFactor = true;
        }
        System.out.println( factor );
    }
 
    public boolean isPrime(long number)
    {
        boolean isNotPrime = false;
        long primeCheck = number - 1;
        while ( primeCheck > 1 && !isNotPrime )
        {
            if ( number % primeCheck == 0 )
            {
                isNotPrime = true;
            }
            primeCheck--;
        }
        if (!isNotPrime)
            return true;
        else
            return false;
            
    }
}

For instance, it will get that 13 is the largest prime factor of 26 just fine, but bigger numbers it can't compute within a reasonable amount of time. In particular I think my math probably isn't up to snuff for this problem, I feel like my solution was very.....roundabout.

okay, turns out the first part to my solution was small

if (isPrime(factor) == true)
                primeFactor = true;
            else
                factorFound = false;

was all I needed to keep the loop going.

Your way of finding prime has potential to be slow. Your loop size could be at most the size of square root of the number you are finding. For example, you are checking whether 123 is a prime. Your loop size should go up to 11 and return true. If you ask for a reason why, it is because the highest number which is to be a factor of any non-prime number is its own square root.

Edited 6 Years Ago by Taywin: n/a

This article has been dead for over six months. Start a new discussion instead.