UVa 294: Divisors

UVa 294: Divisors

Written by on 25 April 2012

Topics: UVa Online Judge

In UVa 294, Divisors, we are asked to find the number with the maximum number of divisors in a given range. Counting number of divisors is a classic problem, and there exists a fast and simple way to do it. We start off with a straight-forward, but slow, implementation and progressively optimize it until it’s fast enough. We don’t stop there, though, but we end with a much faster implementation by noticing that divisor count is related to prime factorization.

Read the problem description here or here.

Interpretation

The problem description is straight-forward and easy to understand, but there are some things we must note before moving forward, that is, and can be as big as and their difference can be as big as . The numbers are too big for a simple-minded approach to work (as said in the problem description), so we have to find a fast algorithm to avoid getting a Time Limit Exceeded verdict from the online judge. Also note that if two or more numbers all have the maximum divisor count, then the smallest one should be selected.

Implementation

We’ll start off by implementing the main method. We loop from to and compute the divisor count, making use of the divisorCount function that we have yet to implement, and keep track of the number with the highest divisor count. Then we output the result in the format described in the problem description.

public static void main(String[] args) throws Exception {
	Scanner in = new Scanner(System.in);
	PrintWriter out = new PrintWriter(System.out, true);

	int tests = in.nextInt(); // read the number of tests

	// for each test
	for (int test = 0; test < tests; test++) {


		int L = in.nextInt(),    // read L
			U = in.nextInt(),    // read U
			maxDivisorCount = 0, // the maximum divisor count found
			maxNumber = 0;       // the number with the maximum divisor count

		// loop through the numbers
		for (int i = L; i <= U; i++) {

			// the divisor count of the current number
			// the divisorCount function calculates it for us
			int currentDivisorCount = divisorCount(i);

			// if the current divisor count is larger than
			// the largest divisor count (a contradiction),
			// then the current divisor count is the
			// largest divisor count
			if (currentDivisorCount > maxDivisorCount) {

				// update appropriate variables
				maxDivisorCount = currentDivisorCount;
				maxNumber = i;
			}
		}

		// output the result in the correct format
		out.printf("Between %d and %d, %d has a maximum of %d divisors.\n", L, U, maxNumber, maxDivisorCount);
	}
}

Now we just have to implement the divisorCount function.

Our first attempt at the divisorCount function will be to loop through all numbers from to and count how many of them are divisors of .

public static int divisorCount(int n) {
	// a counter for the number of divisors
	int count = 0;

	// loop through 1..n
	for (int i = 1; i <= n; i++)
		if (n % i == 0) // if the remainder of n divided by i is 0
			count++;    // then i is a divisor of n

	// return the number of divisors
	return count;
}

This method tests numbers, which is bad. We can do way better…

It’s easy to see that is always a divisor of , and that the second-biggest divisor is at most . We can use that fact to cut our search space in half. Now we can modify our divisorCount function to only check numbers from to .

public static int divisorCount(int n) {
	// a counter for the number of divisors
	// intially 1 because n is a divisor of n
	int count = 1;

	// loop through 1..n/2
	for (int i = 1; i <= n / 2; i++)
		if (n % i == 0) // if the remainder of n divided by i is 0
			count++;    // then i is a divisor of n

	// return the number of divisors
	return count;
}

Now we are only checking numbers, but we can still do one more (but big) optimization to our current method.

Now, let’s say that . Its divisors are . If we split the list into two, and , we see that for each number in the left list, is in the right list. For example, is in the left list and is in the right list. Now we only have to look for numbers in the left list, and for each number we find in that list we increment our divisor counter by, not but , because of the other divisor in the right list. But where does the left list stop, and the right list start? Well, that’s exactly . So in other words, for every divisor below the square root, there exists exactly one divisor above the square root. The only exceptions are square numbers, but we need to be careful not to count their square root twice, since it will be in both lists.

Now we’ll only loop from to , and count each divisor we find, twice.

public static int divisorCount(int n) {
	if (n == 1)    // 1 is a tricky number,
		return 1;  // so we'll handle it separately

	// a counter for the number of divisors
	int count = 0;

	// save the square root to avoid re-computation
	int sqrt = (int)Math.sqrt(n);

	// loop through 1..sqrt(n)
	for (int i = 1; i <= sqrt; i++)
		if (n % i == 0) // if the remainder of n divided by i is 0
			count += 2; // then i and n/i are divisors of n

	// if n is a square number, then
	// we counted sqrt(n) twice
	if (sqrt * sqrt == n)
		count--; // so we fix the count

	// return the number of divisors
	return count;
}

Now we’re only checking numbers, and that is about as good as it gets using this kind of brute-force algorithm to compute the divisor count. Our solution is currently fast enough to get an Accepted verdict, but we can still do better.

Divisor Count through Prime Factorization

We won’t be able to optimize our current algorithm more, so if we want a faster solution, we are going to have to think of a better way than checking each number.

Once again, let’s assume . We all know how to find the prime factors (aka. the prime factorization) of a number (and if not, take a look at Wikipedia), and since we’re trying to find some patterns, we might as well factorize . The prime factorization of is . Now that we’ve factorized , we might as well factorize it’s divisors (smiley-face).

Now we notice that the divisors have very similar prime factorizations to . More precisely, they just have different combinations of the powers of the primes. The powers of range from to (same as the power in ), and the powers of range from to (same as the power in ). Now if we were to count the divisors of , we would use combinatorics and get . Or more generally for any number , where is the -th prime factor and is the power of that prime factor, it’s divisor count is .

Our new algorithm finds the prime factorization of the number, and then computes the divisor count according to our new formula.
Note that I use an optimized trial division, similar to what we did above, to find the prime factorization, but we could also have used a list of primes.

public static int divisorCount(int n) {
	// a counter for the number of divisors
	// intially 1 (the multiplication identity)
	int count = 1;

	// save the square root to avoid re-computation
	int sqrt = (int)Math.sqrt(n);

	// loop through 2 and the odd numbers up to sqrt(n)
	for (int i = 2; i <= sqrt; i = (i == 2 ? 3 : i + 2)) {

		// a counter for the power of the
		// current number in the prime factorization
		int pow = 0;

		// while i is in n's prime factorization
		while (n % i == 0) {
			pow++;  // increment the power count
			n /= i; // remove one i from the prime factorization of n
		}

		// if there were any i's in n's prime factorization
		if (pow != 0) {
			// change the divisor count according to our formula
			count *= pow + 1;

			// recompute the square root, since we've changed n
			// (a little optimization)
			sqrt = (int)Math.sqrt(n);
		}
	}

	// if we've still not removed all factors from n,
	// then there is one prime factor left
	if (n != 1)
		// change the divisor count according to our formula
		// (the power of the last prime is 1)
		count *= 1 + 1;

	// return the number of divisors
	return count;
}

Conclusion

We started with a very slow trial division algorithm, but after some optimizations and some mathematical thinking, we realized that divisor count is related to prime factorization, and used that insight to develop a way faster algorithm. Our current solution is more than fast enough to get an Accepted verdict at the online judge.

If you still want more about divisor count and prime factorization, you might want to take a look at Project Euler 12 and Project Euler 12 – Revisited.

You can take a look at the complete source code here.
So what do you think? Did/would you solve it differently? Let me know in the comments.

8 Comments For This Post I'd Love to Hear Yours!

  1. Mike says:

    If you need to do this for a lot of numbers, you can do:

    for(int n : primes){
    	for(int nn=n; nn<=r; nn+=n){
    		totient[nn]*=(1-1d/n);
    	}
    }
    

    which is equivalent to your method, but avoid repeating work for every number. My programs actually generate the prime list while generating the torient list by noting that a number, i, is prime iff totient[i]=i.

  2. Bjarki Ágúst says:

    First, I don’t understand why you are calculating the totient function?

    But if you’re talking about using a sieve to calculate the divisor counts, it won’t work here since the range we’re working with is too big. We would have to store integers, which needs nearly 4GB of memory. I’m also pretty sure it would be too slow, since we would be going through each number and adding it to the divisor count of all its multiples.

    Please explain if you had something other in mind.

  3. Eman says:

    Hehe absolutely not!!!!

    The limit of numbers you are checking is 10^9 to make a prime factorization of 10^9 you only need sqrt(10^9) = 10^4 * sqrt(10).

    So with this optimalization you can generate primes less than sqrt(10^9). And you also use the sqrt(double) function only once.

    With this you can do the code in 0.024 sec.

    If someone is interested in code, here is C

    #include <stdio.h>
    #include <math.h>
    
    int maxNum;
    int maxDiv;
    int primes[15000];
    int totalPrimes=0;
    
    
    int main()
    {
    
        int cases;
        int a,b;
        int i,j;
    
    
        int PRIME_LIMIT = sqrt(1000000000.0);
        int values[PRIME_LIMIT];
        for(i = 0; i<PRIME_LIMIT; i++)
            values[i] = 0;
    
        for(i = 2; i<PRIME_LIMIT; i++)
            if(values[i] == 0)
            {
                for(j = i+i; j<PRIME_LIMIT; j+=i)
                    values[j] = 1;
                primes[totalPrimes++] = i;
            }
    
    
    
        scanf("%d", &cases);
        for(i = 0; i<cases; i++)
        {
            scanf("%d%d", &a, &b);
            findMax(a,b);
            printf("Between %d and %d, %d has a maximum of %d divisors.\n", a,b,maxNum, maxDiv);
    
        }
    
    
        return 0;
    
    }
    
    void findMax(int a, int b)
    {
    
        maxNum = 0;
        maxDiv = 0;
    
        int i,j;
        int tempDiv;   
        int num;
    
        for(; a<=b; a++)    
        {
            i = 0;
            tempDiv = 1;
            num = a;
    
            while(i < totalPrimes && num != 1)
            {
                j = 1;
                while(num % primes[i] == 0)
                {
                    j++;
                    num /= primes[i];
                }
    
                tempDiv *= j;
                i++;
            }
    
            if(num != 1)
                tempDiv *= 2;
    
            if(maxDiv < tempDiv)
            {
                maxNum = a;
                maxDiv = tempDiv;
            }
        }
    
    }
    
  4. Bjarki Ágúst says:

    0.024 seconds is pretty good. The Java code I wrote for this post ran in 0.140 seconds, but my original C++ code ran in 0.016 seconds.

    But like I mentioned in my post, it can be sped up precalculating primes instead of implicitly finding them each time we calculate the divisor count.

    I have one suggestion for your code, though. On line 65, I would add the following code:

    if (primes[i] * primes[i] > num) break;

    Let me know how if that is faster.

  5. Eman says:

    ok :) best result with all speedups which I was able to do is 0.008 sec.
    With your improvement it runs in a half of that time (0.012 sec). But I changed the code little bit (the change is in method findMax(int, int))

    If (a % 2 == 1) – find the number of divisors of a, increment a
    then (a % 2 == 0) and we can now only roll through even numbers.
    with this improvement my code run in 8 ms. (0.008 sec).

  6. Bjarki Ágúst says:

    I actually tried it out for myself. The line that I suggested was enough to get your solution down to 0.008 sec. Take a look at my last two submissions.

  7. Eman says:

    yop I am quite satisfied with it. And can I contact you here somehow?

  8. Bjarki Ágúst says:

    You can use the Contact Us page.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.