How can I reduce my function runtime

Question

In this code I wanted solve Project Euler Problem #3. The objective is to find the biggest prime number. My code is running right but there is a problem at runtime. How can I reduce run time? Can anyone suggest any tips?

public class Euler3 {

    //https://www.hackerrank.com/contests/projecteuler/challenges/euler003
    public static void main(String[] args) {

        long[] inputs = readInputs();

        for (int i = 0; i < inputs.length; i++) {

            System.out.println(findBiggestPrime(inputs[i]));
        }

    }

    public static boolean isPrime(long num) {

        if (num == 2)
            return true;

        for (long i = 3; i * i <= num; i += 2) {

            if (num % i == 0)
                return false;

        }

        return true;
    }

    private static long[] readInputs() {

        Scanner scanner = new Scanner(System.in);
        int inputQuantities = scanner.nextInt();

        long[] inputs = new long[inputQuantities];

        for (int i = 0; i < inputQuantities; i++) {

            inputs[i] = scanner.nextLong();
        }
        return inputs;
    }

    private static long findBiggestPrime(long number) {

        long biggestPrime = 0;

        if (number % 2 == 0) {

            number = number / 2;
            biggestPrime = 2;
        }

        if (number == 2) 
            return 2;



        for (int i = 3; i <= number; i += 2) {

            if (number % i != 0)  
            continue;

            if(!isPrime(i)) 
                continue;;

                biggestPrime = i;
                number = number / biggestPrime;

        }


        return biggestPrime;
    }


}

You don't have to calculate `i * i <= num` each time. Calculate root of `num` once and use `i<=root`. — Pshemo, Jan 06 '15 at 23:50
This question is more appropriate for codereview.stackexchange.com — John3136, Jan 06 '15 at 23:52
What @John3136 said. If your code works then it is not appropriate for Stack Overflow. If you are looking for a ways to improve your code then you should post it on http://codereview.stackexchange.com/ — Pshemo, Jan 06 '15 at 23:54
You are throwing away all the information about the previous primes and start anew in each iteration of the loop. Note that you only need to check for factors that are themselves primes. — 5gon12eder, Jan 06 '15 at 23:55
[Why do we check up to the square root of a prime number to determine if it is prime?](http://stackoverflow.com/q/5811151/697630) — Edwin Dalorzo, Jan 06 '15 at 23:55
Suppose you already had a list of primes, in order, and that list goes up to at least sqrt(num). What would be the most efficient way to solve the problem? Now, suppose that you have 10 test cases. You construct a list of primes to solve the first test case. Can you think of a way to use the list you've already constructed to solve the next case, instead of starting over from scratch? — ajb, Jan 06 '15 at 23:56
@ajb [Memoization](http://en.wikipedia.org/wiki/Memoization)? — Edwin Dalorzo, Jan 06 '15 at 23:57
Another thing: Your approach tests to see if `number` is divisible by 2, and it divides it by 2 if it is. That is a good thing, because it cuts down on the number of factors you have to test. But what if it's divisible by 4, so that `number/2` is also divisible by 2? — ajb, Jan 07 '15 at 00:00
@ajb If number divisible 4 or 8 like that it doesnt matter because the biggest even prime is 2 — gokhan, Jan 07 '15 at 00:13
You're missing the point. You don't need to divide `number` by 2 at all in order to find the biggest prime. But doing so helps you because it makes your number smaller, so you don't have to check as many odd primes. And your problem is efficiency. So if you can divide it by 4 or 8 or 16, why wouldn't you do that, to make the number even smaller and make your program even more efficient? (This is essentially what pbabcdefp is saying in his answer.) — ajb, Jan 07 '15 at 00:17

Paul Boddington · Accepted Answer · 2015-01-07T01:03:04.323

The lines

if(!isPrime(i)) 
     continue;

will slow down your algorithm and should not be there.

Any factor you encounter in your algorithm should automatically be prime. You should not, for example, ever encounter the factor 15 because you should have already encountered 3 and 5 and divided by them both.

To make this work you should not just do number = number / biggestPrime;. When you encounter a factor you should keep dividing by it until it no longer goes into the number. This way you clear out powers.

Danny Daglas · Answer 2 · 2015-01-07T15:21:59.767

isPrime() is hugely inefficient. Here's a version that keeps track of already-confirmed-multiples in a HashSet. I don't know what order of magnitude of #'s you are using. This seems to work with some efficiency on my machine in the ~100K range.

private static final Set<Long> multiples = new HashSet<>();

private static boolean isPrime(long l) {
    if(l%2==0 && l>2)
        return false;
    if(multiples.contains(l))
        return false;
    double r = Math.sqrt(l);
    for(long i=3;i<=r;++i) {
        for (long j = i * 2; j <= l; j += i) {
            multiples.add(j);
            if (j == l) {
                return false;
            }
        }
    }
    return true;
}

I guess you need `i<=r`, otherwise you could declare numbers like 25 to be prime. — maaartinus, Jan 07 '15 at 02:27

How can I reduce my function runtime

2 Answers2