Project Euler Problem #3

I finally found the answer to problem 3. It certainly isn't an efficient solution being that it's a brute force technique. In fact there are only 4 prime factors to the very large number in the problem. It isn't that they are hard to find, it's checking every number that makes it take so long. The funnest thing about solving these problems is seeing other peoples solutions in the thread - some, if not most, are infinitely better than mine!

 

Problem #3

 

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

What is the largest prime factor of the number 600851475143 ?

 

The first thing you should realize is that you need some sort of algorithm that checks if a number is prime. There are various approaches to this and I've seen some use the sieve method (not very efficient), but I used the simplest one to implement. You put a number into the method and it iterates up to that number, checking if there is any divisors using modular arithmetic (again!).

 

    public static boolean isPrime(long num) {
        boolean prime = false;
        long i;
        for (i=2; i < num ; i++){
        long n = num%i;
        if (n == 0){
            prime = false;
        } else {
            prime = true;
        }
        }
        return prime;
    }

}

 

It returns true if the number is prime and false if the number is not prime.

 

The next part was a bit more tricky, because you have to store a very large number somewhere. You can either use long or a class that handles large numbers, like BigInteger (http://download.oracle.com/javase/6/docs/api/java/math/BigInteger.html). When using long (not to be mistaken with Long!), I found out you have to put an L at the end. I'm not entirely sure why, maybe someone could enlighten me? You should also know that a composite number will not have prime factors exceeding its square root. This is a very important concept that will save us valuable time in our brute force methods.

 

With these important factors in mind, you should know what happens next. A for-loop is needed, iterating from 2 to the square root of 600851475143. First we check if each number is a prime and then we check if that prime evenly divides our large number. If this prime evenly divides our large number, that is a prime factor - what we're looking for!

 

    public static void main(String args[]) {
        long x = 600851475143L;
            for (long i = 2; i*i < x; i++){
            if(isPrime(i) == true) {
                if (x % i == 0){
                    System.out.println("Prime factor: "+i);
                    }
                }
            }

}

 

Very fun and enlightening problem!

 

 EDIT:

I threw in another if-statement that disregards even numbers. It seems to be a tad faster than without it (by milliseconds?). Is there a plug-in for eclipse that shows execution time?

 

 

 

 

Comments

the L is for the compiler to

the L is for the compiler to know that it is an long beside it could be an int or somthing else like 2 is an int 2l ist a long .... execution time is possible by System getTimer ... somthing like that google it :D  

Ah, thanks for your response!

Ah, thanks for your response! That makes a lot of sense.