Need to cut runtime finding divisor of given number

Question

I currently having problem of time limit exceeded for a problem in HackerRank, the problem state to sum all odd divisor of given number. This is my code:

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 is variable that can contains thousands of numbers. I appreciate for any help.

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

You can speed up your code to only find the divisors for the first sqrt(n) numbers. Notice that if i divides N, you also get N/i as the other part of the divisor and the biggest i that you will ever need to check is sqrt(n).

sample code:

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;

Answer 2

One way to decrease runtime would be to only iterate to 1/2 of the number that you are currently finding the odd divisors for. It would look something like this:

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

You don't need to check beyond this halfway point, as a number above that cannot be a divisor of that number.