找到幸运数字实际上是一个问题 - 那些数字之和和数字平方和为质数的数字。我已经实施了埃拉托色尼筛。现在为了进一步优化它，我评论了我的 getDigitSum 方法，我认为它很重并替换为两个硬编码值，但解决一个测试用例仍然需要几分钟。这是对实际问题的参考
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）。