Omar - 8 months ago 52

C Question

Write a program which reads in an integer k, and prints out the number of positive integers

between 1 and 100000 (inclusive) which have exactly k divisors.

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

int main(void){

int k=0, N=0, i=0, r=0, n_divisors=0, result=0;

printf("Enter the number of divisors: ");

/*scanning in an integer value*/

scanf(" %d",&k);

/*loop to count the no. of divisors in an integer from 1 to 100000*/

for(N=1; N<=100000; N++){

n_divisors=0;

/*loop for incrementing the no. divisors in an integer by 2 */

for(i=1; i<sqrt(N); i++ ){

/*Testing if i is a divisor of the integer.*/

r=(N%i);

if( r==0)

n_divisors+=2;

}

/* If the no. of divisors is equal to k, then increment result*/

if(n_divisors==k)

result++;

/* else reset the value of no. of divisors to 0*/

}

/* printing the value for no. of integers form 1 to 100000 with K no. of divisors*/

printf("There are %d numbers between 1 and 100000 inclusive which have exactly \n",result );

printf("%d divisors.",k);

return 0;

}

Answer

It is more serious as you think - you may obtain strange results, not only increased by 1. (See: You count number of divisors by adding `2`

, *as all numbers could have only even numbers of divisors*.)

The problem is in this statement:

```
for(i=1; i<sqrt(N); i++ ){
```

particularly in the expression

```
i<sqrt(N)
```

in it which *excludes* `sqrt(N)`

from possible divisors.

But for numbers which *are* 2nd power of integers (as `1`

, `4`

, `9`

, `16`

, ...) the `sqrt(N)`

** is** their divisor.

So insert into your code something as

```
if (i * i == N)
n_divisors++;
```

so touched part of your code will then look as (I added correct indentations)

```
// loop to count the no. of divisors in an integer from 1 to 100000
for(N=1; N<=100000; N++){
n_divisors=0;
// loop for incrementing the no. divisors in an integer by 2
for(i=1; i<sqrt(N); i++ ){
// Testing if i is a divisor of the integer.
r=(N%i);
if( r==0)
n_divisors+=2;
}
if (i * i == N)
n_divisors++;
// If the no. of divisors is equal to k, then increment result//
if(n_divisors==k)
result++;
// else reset the value of no. of divisors to 0//
}
```

Source (Stackoverflow)