Program taking forever to run

Question

public class Problem_3 {
    public static void main(String... args) {
        long limit = 600851475143L;
        long largestPrimeFactor = 0;

        for (long number = 2; number < limit; number++) {
            if (isPrime(number)) {
                if ((limit % number == 0)){
                    largestPrimeFactor = number; 
                }
            }
        }       
        System.out.println(largestPrimeFactor);
    }

    public static boolean isPrime(long number) {
        for (int i = 2; i < number; i++) {
            if (number % i == 0) {
                return false; 
            }
        }
        return true; 
    }
}

I'm sure, the above program is not in infinite loop. I tested with limit = 13195; and got desired result 29

I don't understand why my CPU is taking forever to run it.

EDIT: Its my code for ProjectEuler.net problem number 3.

You realize that this program has an time complexity of at least O(limit²) — Julien, Sep 05 '13 at 10:24
@Julien what is meant by "time complexity of at least O(limit²)" — SpringLearner, Sep 05 '13 at 10:27
@javaBeginner The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the the input. It's commonly used to describe the performance of an algorithm. The big O notation means when the size of the input goes to infinity. It's an asymptotically description. — Julien, Sep 05 '13 at 10:32
@SnackySrikanth - see http://stackoverflow.com/questions/12025378/project-euler-3-takes-forever-in-java .... one of the main points of ProjectEuler is that the problems are easy to code in a naive way by brute force, but the brute force solution is rarely practical as it will take too long to get the answer. The idea is to come up with a solution that is *much quicker* than a brute force attempt, eg by finding a suitable algorithm. — Qwerky, Sep 05 '13 at 10:51

score 9 · Answer 1 · answered Sep 05 '13 at 10:23

9

Your algorithm has a time complexity of O(n^2), making it not very effective for larger values of your limit.

So it's slow because you're using a poor algorithm.

answered Sep 05 '13 at 10:23

Kayaman

72,141
5
83
121

"time complexity of O(n^2)" ????? can u explain that..?? Noob here. also.. can u suggest a good algorithm..?? – Testaccount Sep 05 '13 at 10:27

Aniket Thakur · Accepted Answer · 2013-09-05T10:42:19.230

5

Time complexity of your code is O(N^2). So it's not a good algorithm for large numbers. A possible suggestion would be as follows -

You are interested in largest prime factor then why not start from the largest value?

    for (long number = limit-1; number > 1; number--) {
        if (isPrime(number)) {
            if ((limit % number == 0)){
                largestPrimeFactor = number;
                 break; 
            }
        }
    }

Though time complexity remains the same this would definitely reduce your time than your present algorithm.

But, what exactly is time complexity..?? and how do u calculate it..?? and what is O(N^2) ?? please explain

 for (long number = 2; number < limit; number++)

Above is your first for loop in which you will have n iterations. Inside this you call isPrime() function which again has a for loop in it for (int i = 2; i < number; i++) again having n iterations. So basically you have two for loops one inside the other which makes your time complexity n*n = n^2

edited Sep 05 '13 at 10:42

answered Sep 05 '13 at 10:29

Aniket Thakur

66,731
38
279
289

As it is right now, it's the same time complexity and you will end with the value 2 as largestPrimeFactor... You should stop lopping when you found one... – Julien Sep 05 '13 at 10:31
@Julien Yes the time complexity is the same but the execution time would surely be less that the present algo. Thanks for pointing out the break in loop :) – Aniket Thakur Sep 05 '13 at 10:33
@AniketThakur thanks a lot for your detailed answer. But, what exactly is time complexity..?? and how do u calculate it..?? and what is O(N^2) ?? please explain.. – Testaccount Sep 05 '13 at 10:35
you should precise that you are speaking of time complexity and not of space complexity. @SnackySrikanth you may want to check this thread http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm – Julien Sep 05 '13 at 10:43
thanks @Julien can u suggest a better way to solve this problem..?? – Testaccount Sep 05 '13 at 10:45
@SnackySrikanth To find the biggest prime inside a specific range of value, this answer is quite good. To check if a specific number is prime, the best algorithm is the AKS primality test – Julien Sep 05 '13 at 10:50

score 2 · Answer 3 · answered Sep 05 '13 at 10:24

2

This is the reason.

long limit = 600851475143L;

and an O(n^2) algorithm and n is this long number 600851475143L

answered Sep 05 '13 at 10:24

sr01853

6,043
1
19
39

score 2 · Answer 4 · answered Sep 05 '13 at 10:34

you are passing each no to the isPrime(long number) method & again you have taken the for loop "for (int i = 2; i < number; i++) {" which is running for another (number-1) every times. means you are running this 600851475141*600851475141 times.

You could have an idea how much time it will take ...........may be you need a super comp for this.....

Happy coding

Vishal Santharam · Answer 5 · 2013-09-05T11:06:04.457

As all said your code is not very time efficient but looking at the code i can guess that you are working to find the biggest prime factor to do that you can actually try Sieve of Eratosthenes to generate all prime then find the factor from back.

import java.util.LinkedList;

 class Sieve{



       public static LinkedList<Long> sieve(long n){
               if(n < 2) return new LinkedList<Long>();
               LinkedList<Long> primes = new LinkedList<Long>();
               LinkedList<Long> nums = new LinkedList<Long>();

               for(long i = 2;i <= n;i++){ //unoptimized
                       nums.add(i);
               }

               while(nums.size() > 0){
                       long nextPrime = nums.remove();
                       for(long i = nextPrime * nextPrime;i <= n;i += nextPrime){
                               nums.removeFirstOccurrence(i);
                       }
                       primes.add(nextPrime);
               }
               return primes;
       }
}

the above code returns the linked list of prime numbers use this start from last and get your largest factor.

NOTE:increase the heap size of jvm before running for the input of 600851475143L

score 1 · Answer 6 · answered Sep 05 '13 at 10:45

Because of the nesting of your loops (one loop up to limit in main and another loop called from within that loop, within isPrime) the time complexity of your algorithm is O(n^2).

This is a standard way to express how long an algorithm takes to solve a different problem for different sized inputs.

In your case, the size is the limit (600851475143L) so to solve the problem up to this will take "an order of 600851475143 ^ 2", compared to, "10 ^ 2 (i.e. 100)", if you had a limit of 10 (for example)

So if the version with a limit of 10 took 100 milliseconds (10 squared), your 600851475143 version would take something like 361022495181519000000000 milliseconds (i.e. 600851475143L squared, apologies if I got some zeroes wrong there)

Other examples of time complexity would be O(1), or constant time, where the algorithm takes the same time regardless of the size, or O(n), or linear time, where the time taken is directly proportional to the size

Program taking forever to run

6 Answers6