Caching 1600 integers and searching from treeSet takes a lot of time What should I use to cache the result so that it takes less time to search?  It currently takes a large number of minutes to complete 10000 test cases with range 1-99999999999999 (18 times 9 - the worst case), even though the search values have been hard-coded for testing purposes (1600, 1501).

Set&lt;Integer&gt; set = new TreeSet&lt;Integer&gt;();
//some logic to populate 1600 numbers
for (int cases = 0; cases &lt; totalCases; cases++) {
    String[] str = br.readLine().split(" ");
    long startRange = Long.parseLong(str[0]);
    long endRange = Long.parseLong(str[1]);
    int luckyCount = 0;
    for (long num = startRange; num &lt;= endRange; num++) {
        int[] longArray = { 1600, 1501 };
        if (set.contains(longArray[0]) &amp;&amp; set.contains(longArray[1])) {
            luckyCount++;
        }

    }
    System.out.println(luckyCount);
}


It actually is a problem to find a lucky number - those numbers whose sum of digits and sum of square of digits are prime. I have implemented the Sieve of Eratosthenes for this.  To optimize it further, I commented my getDigitSum method, and I thought was heavy, so I replaced it with two hard-coded values, but it still takes minutes to solve one test case. Here is a reference to actual problem asked.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Set;
import java.util.TreeSet;

public class Solution {

    private static int[] getDigitSum(long num) {

        long sum = 0;
        long squareSum = 0;
        for (long tempNum = num; tempNum &gt; 0; tempNum = tempNum / 10) {
            if (tempNum &lt; 0) {
                sum = sum + tempNum;
                squareSum = squareSum + (tempNum * tempNum);
            } else {
                long temp = tempNum % 10;
                sum = sum + temp;
                squareSum = squareSum + (temp * temp);

            }
        }
        int[] twosums = new int[2];
        twosums[0] = Integer.parseInt(sum+"");
        twosums[1] = Integer.parseInt(squareSum+"");
        // System.out.println("sum Of digits: " + twoDoubles[0]);
        // System.out.println("squareSum Of digits: " + twoDoubles[1]);
        return twosums;
    }

    public static Set&lt;Integer&gt; getPrimeSet(int maxValue) {
        boolean[] primeArray = new boolean[maxValue + 1];
        for (int i = 2; i &lt; primeArray.length; i++) {
            primeArray[i] = true;
        }
        Set&lt;Integer&gt; primeSet = new TreeSet&lt;Integer&gt;();
        for (int i = 2; i &lt; maxValue; i++) {
            if (primeArray[i]) {
                primeSet.add(i);
                markMutiplesAsComposite(primeArray, i);
            }
        }

        return primeSet;
    }

    public static void markMutiplesAsComposite(boolean[] primeArray, int value) {
        for (int i = 2; i*value &lt; primeArray.length; i++) {
            primeArray[i * value] = false;

        }
    }

    public static void main(String args[]) throws NumberFormatException,
            IOException {
        // getDigitSum(80001001000l);
        //System.out.println(getPrimeSet(1600));
        Set set = getPrimeSet(1600);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int totalCases = Integer.parseInt(br.readLine());
        for (int cases = 0; cases &lt; totalCases; cases++) {
            String[] str = br.readLine().split(" ");
            long startRange = Long.parseLong(str[0]);
            long endRange = Long.parseLong(str[1]);
            int luckyCount = 0;
            for (long num = startRange; num &lt;= endRange; num++) {
                int[] longArray = getDigitSum(num);
                if(set.contains(longArray[0]) &amp;&amp; set.contains(longArray[1])){
                    luckyCount++;
                }
            }
            System.out.println(luckyCount);
        }
    }
}
You claim the lookup in the TreeSet takes a long time, why don't you use a HashSet which guarantees constant time instead of the log(n) time of TreeSet.

Also did you profile your code to verify that it is the lookup that is taking so much time? And that it isn't something else?