java - TreeSet 搜索耗时长，puzzle : to find lucky numbers

Question

找到幸运数字实际上是个问题 - 那些数字的和和数字的平方和是质数的数字。我已经实现了 Sieve of Eratosthenes .现在为了进一步优化它，我评论了我的 getDigitSum 方法，我认为它很重并用两个硬编码值代替，但它仍然需要几分钟来解决一个测试用例。 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 < 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<Integer> getPrimeSet(int maxValue) {
    boolean[] primeArray = new boolean[maxValue + 1];
    for (int i = 2; i < primeArray.length; i++) {
        primeArray[i] = true;
    }
    Set<Integer> primeSet = new TreeSet<Integer>();
    for (int i = 2; i < 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 < 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 < 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 = getDigitSum(num); \\this method was commented for testing purpose and was replaced with any two hardcoded values
            if(set.contains(longArray[0]) && set.contains(longArray[1])){
                luckyCount++;
            }


        }
        System.out.println(luckyCount);
    }

}
}

我应该使用什么来缓存结果，以便花费更少的时间进行搜索，目前它需要大量的时间。分钟完成 10000 个测试用例，范围为 1 99999999999999(18 乘以 9 - 最坏情况)，即使搜索值已被硬编码用于测试目的(1600、1501)。

Answer 1

你需要一个不同的算法。缓存不是你的问题。

如果范围很大——你可以打赌一定会有——即使是一个几乎什么都不做的循环也会花费很长时间。如果我理解正确的话，范围的末尾被限制为不超过 10¹⁸。假设范围的开始是它的一半。然后，您将迭代 5*10¹⁷ 个数字。假设您有一个 2.5 GHz 的 CPU，那么每秒有 2.5*10⁹ 个时钟周期。如果每次迭代都需要一个周期，那就是 2*10⁸ CPU 秒。一年大约有 3.1*10⁷ 秒，因此循环大约需要六年半。

从另一面解决问题。各位数字的平方和最多可以达到18*9²，也就是1458，一个很小的数。数字本身的总和最多可以是 18*9 = 162。

对于小于162的素数，找出所有可能的分解为最多18位数字的和(忽略0)。丢弃那些平方和不是质数的分解。剩下的组合不多了。然后找出在指定范围内您可以使用每种可能的分解构造多少个数字(如果需要，用零填充)。