how can I make this programme faster?

Question

The assignment was to 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. As an example, the number 24 has 8 divisors: 1, 2, 3, 4, 6, 8, 12, and 24.

I have a running programme, but is there anyway i could make the search faster??

#include <stdio.h>
#include <math.h>


int main(void)
{   int a; //user input//
    int divisors; //running total of number of divisors//
    int sum; //running total of numbers with the required number of divisors//

    printf("Enter the target number of divisors:");
    scanf("%d", &a);
    printf("\n");

    int i;
    for (i=1; i<=100000; i++)
    {
            divisors=2;
            int p;
            for(p=2; p<i; p++)
            {if (i%p==0)
            divisors++;}

        if (divisors==a)  
        sum++;}

    printf("There are %d numbers between 1 and 100000 inclusive which have exactly %d divisors.", sum, a);

return 0;
}

Answer 1

Rather than checking for the value of p uptil i we can optimize by checking until sqrt(i) and instead of incrementing divisors by 1, we increament it by 2, one for the number say k divided by i and second for the number i/k.

n=1000000;

for (i=1; i<=10000; i++)
    {
            divisors=2;
            int p;
            for(p=2; p<=sqrt(i); p++)
            {
                if (i%p==0)
                {
                    if(p != (i/p)
                        divisors = divisors + 2;
                    else 
                      divisors++;
                }
            }

        if (divisors==a)  
        sum++;
}

Answer 2

Example code. Moved declarations for i and p to be compatible with old C type compilers (I'm using Microsoft / Visual Studio). Uses ceil(sqrt(i)) outer loops. The code handles an input of 1 (only the number 1 has 1 divisor). An input of 2 will output the number of prime numbers less than 100,000 (there are 9592 prime numbers less than 100,000).

This method takes a bit over 21 million iterations. Number of iterations ~= .67 n sqrt(n).

#include <stdio.h>

int main(void)
{
    int a;          /* user input */
    int divisors;   /* total number of divisors */
    int sum;        /* count of numbers with required number of divisors */
    int i;          /* moved here for C compiler */
    int p;          /* moved here for C compiler */ 
    int sqrti;      /* ceil(sqrt(i)) */

    printf("Enter the target number of divisors: ");
    scanf("%d", &a);
    printf("\n");
    sum = 0;                            /* init sum */
    sqrti = 1;                          /* init sqrti */
    for (i = 1; i <= 100000; i++)
    {
        divisors = 0;                   /* init number of divisors */
        if(sqrti*sqrti < i)             /* update sqrti as needed */
            sqrti += 1;
        for(p = 1; p < sqrti; p++)
            if(i%p == 0)                /* if p is a divisor, count it and i/p */
                divisors += 2;
        if(p*p == i)                    /* if p*p == i, count it */
            divisors += 1;
        if (divisors == a)              /* if i has a divisors, increment sum */
            sum += 1;
    }
    printf("There are %d numbers from 1 to 100000 inclusive which have exactly %d divisors.\n", sum, a);
    return 0;
}

If an array can be used similar to sieve method for primes, this method takes a bit over 1 million iterations. Number of iterations ~= n ln(n).

#include <stdio.h>
#define n 100000
int main(void)
{
int * cnt = (int *)calloc(n+1, sizeof(int));
int d;
    printf("Enter the target number of divisors: ");
    scanf("%d", &d);
    /* time complexity O(n log(n)) */
    {
    int i, j;
        for (i = 1; i <= n; i++) {
            for(j = i; j <= n; j += i) {
                cnt[j]++;
            }
        }
    }
    {
    int i;
    int sum = 0;
        for (i = 1; i <= n; i++)
            sum += (cnt[i] == d) ? 1 : 0;
        printf("excactly %d numbers have %d divisors\n", sum, d); 
    }
    free(cnt);
    return 0;
}