7
\$\begingroup\$

I've solved Project Euler #3, but solving the same in Hacker Rank which has time constraint of < 4 seconds doesn't work. I've tried using the square root solution for speeding up but it fails.

Example:

The prime factors of 10000001 are 11 and 909091, we have sqrt(10000001) = 3162, if we check all primes from 2 to 3162, we can only have 11, after loop terminated, the result will be 11, incorrect answer.

So, when I use num/2 the running time is significantly increased.

public class Solution {

static boolean checkPrime(long num){
boolean toret = true;
long sq = (long) Math.sqrt(num);
for(long i=2; i<=sq; i++){
    if(num%i ==0)
        toret = false;
}
return toret;
}

static long gimmeAns(long num){
ArrayList<Long> al  = new ArrayList<Long>();
int q = 0;
long[] list = new long[10];
long sq = (long)Math.sqrt(num);
long sqint;
boolean flag = true;
if(num < 0){
    for(long i =3; i<=num; i+=2){
    if(num%i == 0)
        al.add(i);
        }
}else{
    //for(long i =3; i<=sq; i+=2){
    //if(num%i == 0)
        //al.add(i);
        //}
    boolean isPrimeCheck = checkPrime(num);
    if(isPrimeCheck){
        al.add(num);
    }
    for(long i =3 ; i<= num/2 ; i+=2){
        if(num%i==0){
            al.add(i);

        }
    }
}
Iterator it = al.iterator();
while(it.hasNext()){
    long curr = (long) it.next();
     flag = true;
    long squrt = (long) Math.sqrt(curr);
        for(long i=2; i<=squrt; i++){
            if(curr%i == 0)
                flag = false;
        }
    if(flag == true){

        list[q++] = curr;
    }
}

return list[q-1];

}

public static void main(String[] args) {
    long numberCases;
    Scanner in = new Scanner(System.in);
    numberCases = in.nextLong();
    long result = 0;
    for(long i=0; i< numberCases; i++){
        long num = in.nextLong();
        result = gimmeAns(num);
        System.out.println(result);
    }

}
}
\$\endgroup\$
2
  • \$\begingroup\$ To clarify, your code works as intended, but is just slower than you would like? \$\endgroup\$
    – Kaz
    Oct 3, 2015 at 18:24
  • \$\begingroup\$ @Zak , yes it works fine but for some unknown case (which HackerRank doesnt disclose) it fails to solve it in less than 4 secs \$\endgroup\$ Oct 3, 2015 at 18:30

1 Answer 1

10
\$\begingroup\$

Format Your Code

It's extremely difficult to follow your logic with inconsistent indenting. 4-spaces after each brace please.

Stop When You Know The Answer

Here is your function to find out if a number is prime. Which you don't actually need for this problem (more on that in a bit), but I wanted to talk about it anyway:

static boolean checkPrime(long num){
    boolean toret = true;
    long sq = (long) Math.sqrt(num);
    for(long i=2; i<=sq; i++){
        if(num%i ==0)
            toret = false;
    }
    return toret;
}

So it is indeed true that you only have to go up to the square root of num. However, let's say we want to find out if 1 trillion is prime. We check 2, and 2 is indeed a divisor. And then we check 3, and 4, and ... and we still check another million numbers. That is hugely inefficient. If you found a divisor, it's already not prime, so just stop:

static boolean checkPrime(long num){
    long sq = (long) Math.sqrt(num);
    for(long i=2; i<=sq; i++){
        if(num%i ==0)
            return false; // we know it's not prime!
    }
    return true;
}

The Algorithm

We want the largest prime factor. We don't care about any other factors, so all the logic around keeping a list (and then going through it again? I don't know what that's about) is unnecessary extra work. Furthermore, you're checking if the number is prime and then going through all the rigmarole of checking all the divisors again. You definitely want to check every divisor at most one time. And even better, divide num as you go:

long largest = 1;
for (long i=2; i*i<=num; ++i) {
    while (num % i == 0) {
        largest = i;
        num /= i;
    }
}

return num > 1 ? num : largest;

So from the Euler example, we start with num == 13195 and i == 2. That doesn't divide, neither does 3 or 4. We get to 5, set largest to 5, and reduce num to 2639. That is no longer divisible by 5. Then we get to 7, largest is now 7 and num is reduced to 377. Then we get to 13, and num is reduced to 29.

At this point we're done, since 14*14 > 29. We know that the remainder must be prime (otherwise we would've found a smaller factor already), so we return 29.

Note that the square root of 13195 is 114, but we didn't even go as high as 14. Your original solution would've have gone up to 114, then gone up to 6597. I just saved you something like 6700 mod operations. And mod operations are not cheap!

Optimization Potential

Once we check for 2, we don't have to check any more even numbers. Once we check for 3, we don't have to check any more multiples of 3. So a simple optimization would be to loop over the factors 5, 7, 11, 13, 17, 19, ... by alternating adding 2 and 4. This is going to be a relatively minor improvement compared to the algorithm improvement I just suggested.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.