1

Resolution:
It turns out there is (probably) "nothing wrong" with the code itself; it is just inefficient. If my math is correct, If I leave it running it will be done by Friday, October 14, 2011. I'll let you know!

Warning: this may contain spoilers if you are trying to solve Project Euler #3.

The problem says this:

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

What is the largest prime factor of the number 600851475143 ?

Here's my attempt to solve it. I'm just starting with Java and programming in general, and I know this isn't the nicest or most efficient solution.

import java.util.ArrayList;

public class Improved {
    public static void main(String[] args) {
        long number = 600851475143L;
        // long number = 13195L;
        long check = number - 1;
        boolean prime = true;

        ArrayList<Number> allPrimes = new ArrayList<Number>();

        do {
            for (long i = check - 1; i > 2; i--) {
                if (check % i == 0) {
                    prime = false;
                }
            }

            if (prime == true && number % check == 0) {
                allPrimes.add(check);
            }

            prime = true;
            check--;
        } while (check > 2);

        System.out.println(allPrimes);
    }
}

When number is set to 13195, the program works just fine, producing the result [29, 13, 7, 5] as it should.

Why doesn't this work for larger values of number?

Closely related (but not dupe): "Integer number too large" error message for 600851475143

Community
  • 1
  • 1
Trufa
  • 39,971
  • 43
  • 126
  • 190

4 Answers4

5

The code is very slow; it is probably correct but will run for an unacceptably large amount of time (about n^2/2 iterations of the innermost loop for an input n). Try computing the factors from smallest to largest, and divide out each factor as you find it, such as:

for (i = 2; i*i <= n; ++i) {
  if (n % i == 0) {
    allPrimes.add(i);
    while (n % i == 0) n /= i;
  }
}
if (n != 1) allPrimes.add(n);

Note that this code will only add prime factors, even without an explicit check for primality.

Jeremiah Willcock
  • 30,161
  • 7
  • 76
  • 78
  • I just added a bug fix, so be sure to get the new version. – Jeremiah Willcock Feb 18 '11 at 15:03
  • There's no reason to save the prime factors in `allPrimes`. When the `for` loop terminates the largest prime factor is left in `n`. This is the answer Project Euler wants. Your code is almost identical to my version and it produces the answer in ~2ms on my machine. – Blastfurnace Feb 19 '11 at 02:10
  • @Blastfurnace: I used the `allPrimes` array since the original code had it. If you wanted to just get the largest factor with my code, you would also need to change the `while` condition to `n % i == 0 && n != i` (to handle numbers such as 9, since `n` would end up as `1` in that case). – Jeremiah Willcock Feb 19 '11 at 02:13
2

Almost all the Project Euler problems can be solved using a signed datatype with 64 bits (with the exception of problems that purposefully try to go big like problem 13).

If your going to be working with primes (hey, its project Euler, your going to be working with primes) get a headstart and implement the Sieve of Eratosthenes, Sieve of Atkin, or Sieve of Sundaram.

One mathematical trick used across many problems is short circuiting finding factors by working to the square root of the target. Anything greater than the square corresponds to a factor less than the square.

Greg Buehler
  • 3,897
  • 3
  • 32
  • 39
0

Another approach (there is no need to store all primes):

private static boolean isOddPrime(long x) {
    /* because x is odd, the even factors can be skipped */
    for ( int i = 3 ; i*i <= x ; i+=2 ) {
        if ( x % i == 0 ) {
            return false;
        }               
    }
    return true;
}

public static void main(String[] args) {
    long nr = 600851475143L;
    long max = 1;
    for ( long i = 3; i <= nr ; i+=2 ) {
        if ( nr % i == 0 ) {
            nr/=i;
            if ( isOddPrime(i) ){
                max = i;
            }
        }   
    }
    System.out.println(max);
}

It takes less than 1 ms.

ROMANIA_engineer
  • 54,432
  • 29
  • 203
  • 199
0

You could also speed this up by only checking from 2 to the square root of the target number. Each factor comes in a pair, one above the square root and one below, so when you find one factor you also find it's pair. In the case of the prime test, once you find any factor you can break out of the loop.

Another optimization could be to find the factors before checking that they are prime.

And for very large numbers, it really is faster to experiment with a sieve rather than brute forcing it, especially if you are testing a lot of numbers for primes. Just be careful you're not doing something algorithmically inefficient to implement the sieve (for example, adding or removing primes from lists will cost you an extra O(n)).

CPhelps
  • 279
  • 1
  • 3
  • 7