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

Question

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<Integer> primes = new ArrayList<>();
    public static Map<Integer, Integer> factorsOccur = new HashMap<>();
    public static List<Integer> factors = new ArrayList<>();

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

        int t = sc.nextInt(), i;

        for (i =0; i < t; i++) {
            int n = sc.nextInt(), temp;
            int k = 0, l = 0;
            fillPrimes(n);
            int curr = primes.get(k);

            if (n %2 != 0) {
                System.out.println(0);
            } else {
                // checking if curr is  factor
                while(curr <= n) {
                    temp = n;
                        while (temp != 0) {
                            if (temp %curr == 0) {
                                l++;    
                                temp /= curr;
                            } else
                                break;
                        }

                        if (l!=0) {
                            factorsOccur.put(curr, l);
                            factors.add(curr);
                        }

                        k++;
                        l=0;

                        if (k >= 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++;
        }

        // get all prime numbers up to the value of n
        if (primes.get(f-1) <= n) {

            int check = 0;
            if (primes.get(f-1) == 2) {
                check = 3;
            } else {
                check =  primes.get(f-1) + 2;
            }
            boolean isPrime = true;
            while (check <= n) {
                for (int i = 0; primes.get(i)*primes.get(i) <= check; i++) {
                    if (check % primes.get(i) == 0) {
                        isPrime = false;
                        break;
                    }
                }

                if (isPrime)
                    primes.add(check);

                isPrime = true;
                check += 2;
            }
        }

    }
}

I don't know how to calculate the time complexity for the code above. But it runs slower than this approach:

• checking if each number (from 1 to square root of n)
• divides n and then if that number is even, and then increment the counter.
• Then we check if the number n/i divides n and then increment the counter once more if it does.

Shouldn't this code run faster than that? Especially for a large number of test cases.

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

public class Solution {

    public static final Scanner sc = new Scanner(System.in);

    public static void main(String... arrgs) {
        int t = sc.nextInt(), n, total, opp;

        for (int i = 0; i < t; i++) {
            n = sc.nextInt();
            total = 0;

            if (n%2 !=0)
                System.out.println(0);
            else {

                for (int j = 2; j*j <= n; j++) {

                    if (j*j == n) {
                        total++;
                    } else {
                        if (n%j == 0) {
                            if (j%2 ==0)
                            total++;

                            opp = n/j;
                            if (n %opp == 0 && opp%2 ==0) {
                                total++;
                            }
                        }
                    }
                }
                total++;
                System.out.println(total);
            }
        }
    }

}

How can I improve the DivisorPrint class so it runs faster than the Solution.

Answer 1

I did a little modification in the class DivisorPrint and in the class Solution if you run both again you will understand why the first is slower.

I change the scanner instantiation to do the process automatically without the need to enter the numbers manually.

public static final Scanner sc = new Scanner(new ByteArrayInputStream("3\n50000000\n60000000\n70000000\n".getBytes()));

So it will run both the programs asking by 3 numbers, that will be: 50.000.000, 60.000.000, 70.000.000.

I put a time counter in your fillPrimes method to compare it with the time taken by the entire execution of Solution program.

If you run this version of DivisorPrint you will get something like:

---

DivisorPrint.java:

Time to fillPrimes (iteration 0): 13 seconds
63
Time to fillPrimes (iteration 1): 4 seconds
128
Time to fillPrimes (iteration 2): 4 seconds
112

---

Solution.java:

63
128
112
time to run the entire program: 2 milliseconds

So... the Solution.java algorithm solve the problem in about 2 milliseconds.

Your optimized method alone took 12 seconds in the first iteration. Even if in the subsequent iterations it taken about 0 millisecons if the subsequent inputs are all covered by the numbers in map, it would only tie the game after about 6K iterations!

The problem is what this type of optimization don't work very well in this context: in the Solution.java code the programmer has used only primitive types and keep the calculation very simple. That map and lists you've used and the related operations, all the autoboxing and unboxing needed, are to much expensive compared to the use of the purest java.

---

The test codes:

import java.io.ByteArrayInputStream;
import java.sql.Time;
import java.util.*;
import java.util.concurrent.TimeUnit;

public class DivisorPrint {

//    public static final Scanner sc = new Scanner(System.in);
    public static final Scanner sc = new Scanner(new ByteArrayInputStream("3\n50000000\n60000000\n70000000\n".getBytes()));
    public static List<Integer> primes = new ArrayList<>();
    public static Map<Integer, Integer> factorsOccur = new HashMap<>();
    public static List<Integer> factors = new ArrayList<>();

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

        int t = sc.nextInt(), i;

        for (i = 0; i < t; i++) {
            int n = sc.nextInt(), temp;
            int k = 0, l = 0;

            long beforeFillPrimes = System.currentTimeMillis();
            fillPrimes(n);
            System.out.println(String.format("Time to fillPrimes (iteration %d): %d seconds", i, TimeUnit.MILLISECONDS.toSeconds(System.currentTimeMillis() - beforeFillPrimes)));

            int curr = primes.get(k);

            if (n % 2 != 0) {
                System.out.println(0);
            } else {
                // checking if curr is  factor
                while (curr <= n) {
                    temp = n;
                    while (temp != 0) {
                        if (temp % curr == 0) {
                            l++;
                            temp /= curr;
                        } else
                            break;
                    }

                    if (l != 0) {
                        factorsOccur.put(curr, l);
                        factors.add(curr);
                    }

                    k++;
                    l = 0;

                    if (k >= 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++;
        }

        // get all prime numbers up to the value of n
        if (primes.get(f - 1) <= n) {

            int check = 0;
            if (primes.get(f - 1) == 2) {
                check = 3;
            } else {
                check = primes.get(f - 1) + 2;
            }
            boolean isPrime = true;
            while (check <= n) {
                for (int i = 0; primes.get(i) * primes.get(i) <= check; i++) {
                    if (check % primes.get(i) == 0) {
                        isPrime = false;
                        break;
                    }
                }

                if (isPrime)
                    primes.add(check);

                isPrime = true;
                check += 2;
            }
        }

    }
}

---

import java.io.ByteArrayInputStream;
import java.util.Scanner;

public class Solution {

//    public static final Scanner sc = new Scanner(System.in);
    public static final Scanner sc = new Scanner(new ByteArrayInputStream("3\n50000000\n60000000\n70000000\n".getBytes()));

    public static void main(String... arrgs) {
        int t = sc.nextInt(), n, total, opp;
        long before = System.currentTimeMillis();


        for (int i = 0; i < t; i++) {
            n = sc.nextInt();


            total = 0;

            if (n % 2 != 0)
                System.out.println(0);
            else {

                for (int j = 2; j * j <= n; j++) {

                    if (j * j == n) {
                        total++;
                    } else {
                        if (n % j == 0) {
                            if (j % 2 == 0)
                                total++;

                            opp = n / j;
                            if (n % opp == 0 && opp % 2 == 0) {
                                total++;
                            }
                        }
                    }
                }
                total++;
                System.out.println(total);
            }

        }

        System.out.println(String.format("time to run the entire program: %d milliseconds", (System.currentTimeMillis() - before)));
    }

}

Answer 2

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<Integer> 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) {
        for (int prime : oddPrimes) {
            if (prime > n / prime) {
                return true;
            }

            if (n % prime == 0) {
                return false;
            }
        }

        return true;
    }