Making solution for Project Euler more efficient.

Question

Hey everyone,

Originally, I was having some issues getting this code to function, but after a little tweaking I got it debugged and ready to go.

I have gone through several revisions of this program. I started with integer values only to find that the number was too large to fit into an int. I then changed to BigIntegers, which proved to be a hassle, but workable. From there, I switched to longs (as should have done from the beginning) and cut the runtime of my code 8-fold (or more).

Here's the code as it is now:

long qNum = 600851475143L;

for (long i = qNum - 1L; i * i >= qNum; i -= 2L)
    if (qNum % i == 0 && isPrime(i)) {
        System.out.println("Solution:" + i); // for debugging
        return i;
    }
    else
        System.out.println(i);// for debugging

return 0L;

And

public static boolean isPrime(long num) {
    // unnecessary if statement for this problem (b/c of for loop), but useful for others 
    if (num % 2 == 0)
        return false;

    for (long i = 3; i * i <= num; i += 2)
        if (num % i == 0)
            return false;

    return true;
}

It's been running for multiple hours and it still hasn't found anything. I saw online that solving this puzzle the typical way is like parsing 560GB of data =/.

Any tips for speeding this up?

Many thanks,

Justian

EDIT:

Optimized code:

public static long greatestPrimeFactor(ArrayList<Long> factors, long num) {
    for (long i = 2; i <= Math.sqrt(num); i++) {
        if (num % i == 0) {
            factors.add(i);
            return greatestPrimeFactor(factors, num / i);
        }
    }

    for (int i = factors.size()-1; i > 0; i--)
        if (isPrime(factors.get(i)))
            return num;

    return 0;
}

AND

public static boolean isPrime(long num) {
if (num % 2 == 0)
    return false;

for (long i = 3; i * i <= num; i += 2)
    if (num % i == 0)
        return false;

    return true;
}

RUN WITH

greatestPrimeFactor(new ArrayList<Long>(), 600851475143L);

Answer 1

My solution hits in less than a hundredth of a second. Each time you find a divisor of the number, divide the number by that divisor and start again. The highest number you divide by is your target.

Answer 2

You don't need to test every number for whether or not it is prime. You see this, so you only test every ODD number (well, and 2). You can take this further! Construct a table of the first few million primes quickly, and only test against those. You'll go a LOT faster, with a very small overhead.

Edit: Here's what I was talking about. It's quite straightforward. Notice how I only compare the values to already computed primes. Once you've computed a fair number of them (say, the first 10000000 primes) start doing your search based on on the +2 method like you are. Keep in mind that most of them are going to get caught early because you're skipping unnecessary numbers. You don't need to test 15,25,35,45,55, etc, because you already tested 5. That in and of itself is going to cull about 20% of your tests, which easily accounts for the overhead of calculating the first few million numbers.

Sample output

C:\files\j\misc>java sandbox2
resized to 200
resized to 400
resized to 800
resized to 1600
resized to 3200
resized to 6400
resized to 12800
resized to 25600
resized to 51200
resized to 102400
resized to 204800
resized to 409600
resized to 819200
664579 primes in 18 seconds. Last prime was 9999991

C:\files\j\misc>

Sample code:

public class sandbox2 {
    static int[] primes = new int[100]; // where the primes really are
    static int count = 0;
    static long mostRecentPrime;

    public static void main(String[] args) throws Exception {
        addPrime(2); // give it a couple to start
        addPrime(3);
        addPrime(5);
        long start = System.currentTimeMillis();
        for(long i = 7; i < 10000000; i++) { // all primes less than 10M
            if(isPrime(i)) addPrime(i);            
        }        
        long end = System.currentTimeMillis();
        long time = (end-start) / 1000;
        System.out.println(count + " primes in " + time + " seconds. Last prime was " + mostRecentPrime);
    }    
    public static boolean isPrime(long i) {
        long max = (long)(Math.sqrt(i))+1;
        for(int pos = 0; primes[pos] < max && pos < primes.length; pos++) {
            long prime = (long)(primes[pos]);
            if(i % prime == 0) return false;
        }
        return true;
    }    
    public static void addPrime(long p) {
        mostRecentPrime = p;
        if(count == primes.length) { // resize if necessary
            int size = primes.length * 2;
            int[] newprimes = new int[size];
            System.arraycopy(primes, 0, newprimes, 0, primes.length);
            primes = newprimes;
            System.out.println("resized to " + primes.length);
        }
        primes[(int)count] = (int)p;
        count++;
    }
}

Answer 3

You are doing too many unnecessary things. Here's a simpler solution:

long greatestFactor(long n) {
    long p = 0;
    for (long k = 2; k * k <= n; k++)
        while (n % k == 0) {
            n /= k;
            p = k;
        }
    if (n > 1)
        p = n;
    return p;
}