java - 需要削减给定数字的运行时查找除数

Question

我目前遇到 HackerRank 中的问题超出时间限制的问题，问题状态是对给定数字的所有奇数除数求和。这是我的代码:

int[] numbers = {21, 11, 7};

    long total = 0;
    for (int i = 0; i < numbers.length; i++) {
        for (int j = 1; j <= numbers[i]; j+=2) {
            if (numbers[i] % j == 0) {
                total += (long) j;
            }
        }
    }

int[] numbers 是可变的，可以包含数千个数字。感谢您的帮助。

int[] numbers = {
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7,
        21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7, 21, 11, 7};

Answer 1

您可以加快代码的速度，使其只查找第一个 sqrt(n) 数字的除数。请注意，如果我除以 N，您还会得到 N/i 作为除数的另一部分，而您需要检查的最大 i 是 sqrt(n)。

示例代码:

int sum = 0;
for(int n : all the numbers){
    for(int i = 1; i*i<=n;i++){
        if(n%i == 0){
            if(i % 2 == 1)sum+=i;
            if((n/i) % 2 == 1)sum += (n/i);
        }
    }
}
return sum;