How can I optimize this Java code for speed?

Some thoughts on speed:

• Start caching results in isPrime.
• Print things as soon as you calculate them, no need to store them back into an array. (This makes debugging easier, too.)
  • As Leonid pointed out, storing things may be a good idea. I would keep it an array in that case, not a linked list, as that costs less time.
  • However, I would simply disable output when profiling, and keep my suggestion for debugging.
  • On a similar note, consider splitting both the main algorithm and the output into separate functions so that you can easily disable both. That makes it much easier to check how much each stage of the algorithm (parsing, processing, printing) is taking.
• You could try caching rem*rem, as you know there's only ten possibilities. May be faster, may be slower.
• You should take a look at the input you'll be dealing with and figure out what values your program needs to have that could be given beforehand. What values can the numbers you're checking for primality be? (I would guess you need up to around 2000, but I'm not sure.)

Some general thoughts:

• Add some comments. What is a lucky number?
• Add some blank lines.
• Rename getLucky to isLucky or checkIsLucky. I'd go for the first, but some people will tell you that functions need a verb other than "is". If Java supports it, you could make it an extension method and then do arr[i].isLucky().
• Don't make variables static unless they have to be. Both T and ans can be local to main.
• Make your variable names more meaningful. In particular, replacing T with numberOfInputPairs (or numInputPairs, at least) would improve matters.
• Don't use the same name for two variables, with one letter difference. Why do you have sum and sum1? What's the difference between them?
• Use the += operator when possible. sum1 += rem*rem is easier to read than what you have.

To address the question of numberOfInputPairs being too long: let's reformat the code a little and change the name appropriately:

public static void main(String ar[]){
    Scanner scan = new Scanner(System.in);
    int numberOfInputPairs = scan.nextInt();
    int ans[] = new int[numberOfInputPairs];

    for (int i = 0; i < numberOfInputPairs; i++){
        A = scan.nextLong();
        B = scan.nextLong();
        for (long j = A; j <= B; j++) {
            if (getLucky(j)) {
                ans[i]++;
            }
        }
    }

    for (int i = 0; i < numberOfInputPairs; i++) {
        System.out.println(ans[i]);
    }
}

Yes, if no whitespace is added, the longer variable names make a wall of text a bigger wall of text, and convey very little meaning. However, with just a slight increase in the amount of whitespace, I find that the longer variable name is no less clear and makes it clear what is being done.

(By the way, I think this is partially a language problem: as things are, it is used three times, while a proper for-each loop would mean it would only need to be used once.)

I do not agree with n or T offering that clarity; numPairs would do, too, and is down to personal preference.

I think you chould consider improving the isPrime(long sum) (i don't think sum is a luckily chosen name here, by the way).

Consider using a better algorythm, e.g. a sieve fo atkin instead of looping all values.

See e.g. this implementation

On this basis you can improve caching on your specific needs.

I would give you the advice to optimize your code for readability and start measuring. Only pull in optimizations that are worth. Don't clutter up your code without value.

Code optimization can be tricky. Make the code optimal can be something different.

There's a lot of sub-question: Optimization, in term of speed / memory ? On which device? From a fresh start, or after a long running time ?

But first, give variable a explicit name, because A,B,T means nothing to me/ others code, and longer variable name won't slow down your code. Second, use a profiler may help you, I usually use jvisualvm.exe (in the jdk). Third, a faster code on your machine won't necessary be faster on a other computer / device.

In your getLucky method, the lucky variable is not necessary, you could do: return (isPrime(sum)&&isPrime(sum1));

but it will render your code less readable.

In your isPrime method, the for loop check the i is a integer and the sum is a long. So if the sum is bigger than MAX_INTEGER you will be in trouble.

Not sure about optimisation, but I think readability is really important, and conciseness is a big part of readability. So I would write the isPrime method like this.

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

Also, lots of work has been done on good algorithms for testing primality. Running through and testing for divisibility by every integer is far from optimal. So you could do some research on this - it's a mathematics question, not a computer science one.

One idea that you could try is the whole difference of squares thing. If you've got an array in which you've stored lots of square numbers, then you can use this to test with subtraction, rather than division. That is, if you're testing some odd number z, which happens to be x * y, then it's also

((x+y)/2)^2 - ((x-y)/2)^2

And since x and y must both be odd, both of the entities being squared are integers. So looking for two squares that differ by z turns out to be equivalent to looking for factors, but computationally much easier.

Have a try at turning this approach into Java code. Post a comment on this answer if you get stuck, and I'll try to give you some more guidance.

isPrime(long num) method can be improved by using other prime number checking algorithms such as Fermat theoram, reducing check space or by simply incrementing by 2 instead of i++.You don't need to check every even number upto n.Infact, you don't need to check every odd number upto n.just check it upto sqrt(number).

eg ->

      if(num%2==0)
        return false;
      for(i=3;(i*i)<num;i+=2)
      {
       .............
      } 

    onw more 

For more details , refer to 1st chapter of Fundamentals of Algorithms by Sahni