Finding all the divisors of a given number, that are even

What this code is basically supposed to do is find how many even divisors a number has.

For example the number 100 has the divisors 1, 2, 4, 5, 10, 20, 25, 50, 100 of which 6 (2, 4, 10, 20, 50 and 100) are even. So we output 6.

The first line of input is supposed to be the number of test cases (t). And for each of the following t numbers, we have to calculate the number of even divisors.

```
import java.math.*;
import java.io.*;
import java.util.*;

public class DivisorPrint {

public static final Scanner sc = new Scanner(System.in);
public static List primes = new ArrayList<>();
public static Map factorsOccur = new HashMap<>();
public static List factors = new ArrayList<>();

public static void main(String... arrgs){

int t = sc.nextInt(), i;

for (i =0; i = primes.size())
break;
else
curr = primes.get(k);
}

// now we have the list of primes
Collections.sort(factors);

if (n == 2) {
System.out.println(1);
} else {
int occurTwo = factorsOccur.get(factors.get(0));
int total = 0;

if (factors.size() ==1) {
total = occurTwo;
} else {
total = 1;
for (int r = 1; r < factors.size(); r++) {
total *= (factorsOccur.get(factors.get(r)) + 1);
}

total *= occurTwo;
}

System.out.println(total);

}

}
factorsOccur.clear();
factors.clear();
}
}

public static void fillPrimes(int n) {
int f = primes.size();
if (f == 0) {
// there are no primes
primes.add(2);
f++;

Time complexity

Your second version (Solution) is \$\mathcal{O}(\sqrt{n})\$.

Your first version (DivisorPrint) takes an \$\mathcal{O}(\frac{n \cdot \sqrt{n}}{\ln{n}})\$ operation to find primes. But it only does this some of the time. You save it for the future, but for a small number of test cases, this will dominate.

Note that \$\frac{2 \cdot \sqrt{n}}{\ln{n}}\$ is an estimate of the number of primes up to \$\sqrt{n}\$.

For a given test case, you are checking \$\mathcal{O}(\frac{\sqrt{n}}{\ln{n}})\$ primes to see if they are factors. So if there are fewer than \$\mathcal{O}(n)\$ test cases, finding the primes dominates the time complexity.

If you want DivisorPrint to be faster than Solution, you need to precalculate the primes so that you don't have to list them out each time.

That said, it is possible to make both more efficient.

Solution

public static int countEvenFactors(int n) {
        if (n % 2 != 0) {
            return 0;
        }

        int total = 1;
        int j = 2;
        for (; j*j < n; j += 2) {
            if (n % j == 0) {
                int quotient = n / j;
                total++;

                if (quotient % 2 == 0) {
                    total++;
                }
            }

            int quotient = n / (j + 1);
            if (n % quotient == 0 && quotient % 2 == 0) {
                total++;
            }
        }

        return (j*j == n) ? total + 1 : total;
    }

This version is more flexible. It returns the count of the even factors rather than printing them.

It moves declarations to the initialization spot and moves initialization as close to first use as possible. So if you don't need a variable, it doesn't declare it.

Your original version checks on each iteration if j is the square root of n. This checks that just once, since it will only be true on the last iteration.

As noted in a comment, your original version increments by one and then checks for evenness. This version increments by two, so it's always even. To get the quotients of the odd factors, we add one to j.

DivisorPrint

public static final Scanner sc = new Scanner(System.in);
public static List oddPrimes = new ArrayList<>();

These are the only class variables needed with my revised versions.

public static void main(String... arrgs){
        for (int t = sc.nextInt(); t > 0; t--) {
            int n = sc.nextInt();
            fillPrimes(n);

            System.out.println(countEvenFactors(n));
        }
    }

This version of main is simpler. No i variable at all.

Most of the complexity is now hidden in the countEvenFactors method.

public static int countEvenFactors(int n) {
        if (n % 2 != 0) {
            return 0;
        }

        int total = 0;
        while (n != 0 && n % 2 == 0) {
            n /= 2;
            total++;
        }

        for (int prime : oddPrimes) {
            int l = 1;
            while (n > 1 && n % prime == 0) {
                n /= prime;
                l++;
            }

            total *= l;

            if (n <= 1) {
                break;
            }
        }

        return total;
    }

Since we have to treat two differently from every other prime, I pulled it out and did it first.

We don't have to divide until zero. One is sufficient.

I changed the outer loop to loop over the oddPrimes. This makes it simpler, although it means that I have to do the comparison to n separately. But we no longer need i and we don't have to constantly do oddPrimes.get(i).

Because we do two separately, we can initialize l to one. So we can just multiply. We don't have to add one or check that it's not zero.

We don't have to store factorsOccur. We can just multiply immediately.

We never needed factors, as we could just do factorsOccur.keySet(). But here we don't even do that.

We don't need to sort factors. We don't need to do them in ascending order, and if we did, oddPrimes will be in ascending order.

I moved the divisibility check into the while condition. No more break statement in the while.

public static void fillPrimes(int n) {
        int nextCandidate = 3;
        if (!oddPrimes.isEmpty()) {
            nextCandidate = oddPrimes.get(oddPrimes.size() - 1) + 2;
        }

        for (; nextCandidate <= n; nextCandidate += 2) {
            if (isPrime(nextCandidate)) {
                oddPrimes.add(nextCandidate);
            }
        }
    }

We don't need f. We only need the size once, to get the most recent (largest) prime. The rest of the logic is the same regardless, since we aren't finding the even prime (there's only one).

We could write the whole thing in the for loop, but it makes the declaration rather long. I find this easier to follow.

Moving the isPrime check into its own method saves us an isPrime variable.

```
public static boolean isPrime(int n) {

StackExchange Code Review Q#155833, answer score: 3