Program to display array elements in the ascending order of number of factors each element has

Question

Input:

1000 23 100 26 32

Output:

23  26  32  100 1000

Since 23 has '2' factors and 26 has '4' factors and 32 has '6' factors, and so on.

1. Should I use a linked list for these types of problems?

2. Is my code efficient? Or how can it be optimized?

Code:

#include <stdio.h>
#include <stdlib.h>

int facts(int);

int main(void) {
    int n,a[2][25],i,j;
    printf("Enter the no. of items\n");
    scanf("%d",&n);
    printf("Enter the items\n");
    for(j=0; j<n; j++)
    {
        scanf("%d",&a[0][j]);
    }
    for(j=0; j<n; j++)
    {
        a[1][j] = facts(a[i][j]);
    }

    for(int x=0; x<n; x++)
    {
        for(int y=0; y<n-1; y++)
        {
            if(a[1][y]>a[1][y+1])
            {
                int temp = a[1][y+1];
                int temp1 = a[0][y+1];
                a[1][y+1] = a[1][y];
                a[0][y+1] = a[0][y];
                a[1][y] = temp;
                a[0][y] = temp1;
            }
        }
    }

    for(j=0; j<n; j++)
        {
            printf("%d\t", a[0][j]);
        }

    return 0;
}

int facts(int h)
{
    int factors=0;
    for(int k=1; k<=h; k++)
    {
        if((h%k)==0)
        {
            factors++;
        }
    }
    return factors;
}

Answer 1

int main(void) {
    int n,a[2][25],i,j;
    printf("Enter the no. of items\n");
    scanf("%d",&n);
    printf("Enter the items\n");
    for(j=0; j<n; j++)
    {
        scanf("%d",&a[0][j]);
    }
    for(j=0; j<n; j++)
    {
        a[1][j] = facts(a[i][j]);         // here i is not set yet
    }

Your compiler should've warned you about this. Please make sure all variables have a set value before checking them.

The only reasons this works is because your compiler decided to initialize i at zero here. However, it is not required to do so by the specification. This means it will break on other systems.

Answer 2

To start with...

Use better variable names!

printf("Enter the no. of items\n");
scanf("%d",&n);

n is the number of items. So, it's not int n, it's int numberOfItems.

printf("Enter the items\n");
for(j=0; j<n; j++)
{
    scanf("%d",&a[0][j]);
}

a contains the items. So, it's not int a[2][25], it's int items[2][25].

By going through your variables and giving them more detailed names, it'll be easier to understand what your code does - both for yourself and for anyone else who has to read it.

Answer 3

Even after taking into account Cherubim Anand's good answer, you can still make facts faster using a better algorithm based on mathematical properties like:

$$if n = \prod_{i=1}^r p_i^{a_i}, facts(n)=\prod_{i=1}^r (a_i+1).$$

Thus, iterating over number to identify prime factors and their exponents, you can easily determine the number of factors.

int facts3(int n)
{
    if (n <= 2)
        return n;
    int facts = 1;
    for (int d = 2; d * d <= n; d++)
    {
        int pow = 0;
        nb_mod_facts3++;
        while (n % d == 0)
        {
            n /= d;
            pow++;
        }
        facts *= (pow + 1);
    }
    if (n > 1)  // remaining prime factor (with exp 1)
    {
        int pow = 1;
        facts *= (pow + 1);
    }
    return facts;
}

Some more improvement (visible below) could be used (make d go though 2 and then only odd values) but the major point is to use the formula above.

Benchmark:

I've used the following code to ensure that the different functions lead to similar results (after some minor adjustment) and to evaluate the performances by counting the number of modulo operations.

#include <stdio.h>

int nb_mod_facts1 = 0;
int nb_mod_facts2 = 0;
int nb_mod_facts3 = 0;
int nb_mod_facts4 = 0;

int facts(int h)
{
    int factors=0;
    for(int k=1; k<=h; k++)
    {
        nb_mod_facts1++;
        if((h%k)==0)
        {
            factors++;
        }
    }
    return factors;
}

int facts2(int n)
{
    if (n <= 2)
        return n;
    int factors = 2; //as 1 and number itself are already considered as factors
    for(int k=2; k<=(n/2); k++)
    {
        nb_mod_facts2++;
        if((n%k)==0)
        {
            factors++;
        }
    }
    return factors;
}

int facts3(int n)
{
    if (n <= 2)
        return n;
    int facts = 1;
    for (int d = 2; d * d <= n; d++)
    {
        int pow = 0;
        nb_mod_facts3++;
        while (n % d == 0)
        {
            n /= d;
            pow++;
            nb_mod_facts3++;
        }
        facts *= (pow + 1);
    }
    if (n > 1)  // remaining prime factor (with exp 1)
    {
        int pow = 1;
        facts *= (pow + 1);
    }
    return facts;
}

int facts4(int n)
{
    if (n <= 2)
        return n;
    int facts = 1;
    // Consider 2 as special
    {
        int d = 2;
        int pow = 0;
        nb_mod_facts4++;
        while (n % d == 0)
        {
            n /= d;
            pow++;
            nb_mod_facts4++;
        }
        facts *= (pow + 1);
    }
    for (int d = 3; d * d <= n; d+=2)
    {
        int pow = 0;
        nb_mod_facts4++;
        while (n % d == 0)
        {
            n /= d;
            pow++;
            nb_mod_facts4++;
        }
        facts *= (pow + 1);
    }
    if (n > 1)  // remaining prime factor (with exp 1)
    {
        int pow = 1;
        facts *= (pow + 1);
    }
    return facts;
}


int main(int argc, char* argv[])
{
    for (int i = 0; i < 29999; i++)
    {
        int f1 = facts(i);
        int f2 = facts2(i);
        int f3 = facts3(i);
        int f4 = facts4(i);
        if (f1 != f2)
            printf("Something wrong for i=%d : f1:%d != f2:%d\n", i, f1, f2);
        if (f1 != f3)
            printf("Something wrong for i=%d : f1:%d != f3:%d\n", i, f1, f3);
        if (f1 != f4)
            printf("Something wrong for i=%d : f1:%d != f4:%d\n", i, f1, f4);
    }
    printf("Number of modulo operations : %d %d %d %d\n", nb_mod_facts1, nb_mod_facts2, nb_mod_facts3, nb_mod_facts4);
    printf("Speed factor : %d %d %d %d\n", nb_mod_facts1/nb_mod_facts1, nb_mod_facts1/nb_mod_facts2, nb_mod_facts1/nb_mod_facts3, nb_mod_facts1/nb_mod_facts4);
    return 0;
}

The results are the following :

Number of modulo operations : 449955001 224940004 1287262 703821

Speed factor : 1 2 349 639

---

Also please note that facts may not be the best name as I may lead to confusion with factorial often being called fact.

Answer 4

Finding the number of factors using facts() function can be done more efficiently

---

Fact 1 : for any number 1 and the number itself are factors

• So, instead of initializing factors to 0, initialize with 2 ( because 1 and number are always factors)

---

Fact 2: for any number the greatest factor other than itself is always less than or equal to number/2

Ex : 24

//factors :

1  * 24
2  * 12
3  *  8
4  *  6 
6  *  4
8  *  3
12 *  2 //see it's equal to half of the number (24/2 = )12
24 *  1

• more specifically if the number is even, then highest factor (other than number itself) is equal to number/2 and if the number is odd, then it's highest factor is less than it's half, time to take a paper and checkout! :)

so, using the above fact

for(int k=1; k<=h; k++)

can be modified to

for(int k=2; k<=(h/2); k++) //k=2 since we initialize `factors = 2`

---

so from the above two facts, the facts() function can be modified to :

int facts(int h)
{
    int factors = 2; //as 1 and number itself are already considered as factors
    for(int k=2; k<=(h/2); k++)
    {
        if((h%k)==0)
        {
            factors++;
        }
    }
    return factors;
}

---

• Additionally, here in your code : a[2][25] , you are assigning memory statically but, if the number of elements of the array is dependent on user's input, then better allocate memory dynamically to a *pointer using the malloc() function provided by the stdlib.h library file.

Example :

#include <stdlib.h> //don't forget this
#include <stdio.h>

int main(void) 
{
    int n,i,j;
    int *a[2]; //the ponter

    printf("Enter the no. of items\n");
    scanf("%d",&n); //scanning number of elements

    for(int index = 0; index<2 ; index++)
    {
        a[index] = malloc(n*sizeof(int)); //allocating memory

        if(a[index] == NULL) //checking if memory was successfully allocated or not
        {
            printf("memory allocation problem :(");
            exit(1); //exit unsuccessfully
        }
    }

    //continue logic.....

    //and at the end
    for(int index=0 ; index<2; index++)
        free(a[index]) //don' forget to free allocated memory

}//end of main function

Note :

• Don't forget to check for return value of malloc() with if(pointer==NULL)

• Don't forget to free() the allocated memory by sending appropriate pointer as argument.