Getting one too few divisors

Question

This is a program to count the number of divisors for a number, but it is giving one less divisor than there actually is for that number.

#include <stdio.h>

int i = 20;
int divisor;
int total;

int main()
{
    for (divisor = 1; divisor <= i; divisor++)
    {
        if ((i % divisor == 0) && (i != divisor))
        {
            total = total++;
        }
    }
    printf("%d %d\n", i, total);
    return 0;
}

The number 20 has 6 divisors, but the program says that there are 5 divisors.

Answer 1

&& (i != divisor)

means that 20 won't be considered a divisor. If you want it to be considered, ditch that bit of code, and you'll get the whole set, {1, 2, 4, 5, 10, 20}.

Even if you didn't want the number counted as a divisor, you could still ditch that code and just use < instead of <= in the for statement.

And:

total = total++;

is totally unnecessary. It may even be undefined, I'm just too lazy to check at the moment and it's not important since nobody writes code like that for long :-)

Use either:

total = total + 1;

or (better):

total++;

Answer 2

Divisor counting is perhaps simpler and certainly faster than any of these. The key fact to note is that if p is a divisor of n, then so is n/p. Whenever p is not the square root of n, then you get TWO divisors per division test, not one.

int divcount(int n)
{
    int i, j, count=0;
    for (i=1, j=n; i<j; j = n/++i)
    {
        if (i*j == n)
            count += 2;
    }
    if (i == j && i*j == n)
        ++count;
    return count;
}

That gets the job done with sqrt(n) divisions, and sqrt(n) multiplications. I choose that because, while j=n/i and another j%i can be done with a single division instruction on most CPUs, I haven't seen compilers pick up on that optimization. Since multiplication is single-clock on modern desktop processors, the i*j == n test is much cheaper than a second division.

PS: If you need a list of divisors, they come up in the loop as i and j values, and perhaps as the i==j==sqrt(n) value at the end, if n is a square.

Answer 3

You have added an extra check && (i != divisor) as explained in given answer.

Here, I wrote the same program using the prime factorisation. This is quick way to find the number of divisor for large number (reference).

// this function return the number of divisor for n.
// if n = (m^a) (n^b) ... where m, n.. are prime factors of n
// then number of divisor  d(n) = (a+1)*(b+1)..
int divisorcount(int n){

  int divider = 2;
  int limit = n/2;
  int divisorCount = 1;
  int power = 0;

  // loop through i=2...n/2
  while(divider<=limit){
    if(n%divider==0){
      // dividing numper using prime factor
      // (as smallest number devide a number 
      // is it's prime factor) and increase the
      // power term for prime factor.
     power++;
     n/=divider;
    }
    else{
      if(power != 0){
        // use the prime factor count to calculate
        // divisor count.
        divisorCount*=(power+1);
      }
      power = 0;
      divider++;
    // if n become 1 then we have completed the 
    // prime factorization of n.
    if(n==1){
      break;
    }

    }
  }
return divisorCount;
}