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 set = new TreeSet();
//some logic to populate 1600 numbers
for (int cases = 0; cases < 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 <= endRange; num++) {
        int[] longArray = { 1600, 1501 };
        if (set.contains(longArray[0]) && 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 > 0; tempNum = tempNum / 10) {
if (tempNum getPrimeSet(int maxValue) {
boolean[] primeArray = new boolean[maxValue + 1];
for (int i = 2; i primeSet = new TreeSet();
for (int i = 2; i < maxValue; i++) {
if (primeArray[i]) {
primeSet.add(i);
markMutiplesAsComposite(primeArray, i);
}
}

return primeSet;
}

public static void markMut

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?

StackExchange Code Review Q#16369, answer score: 3