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

### 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;
}

• Your code is broken. The variable i is not initialized before it is used as an index in a for loop. – pacmaninbw Jun 28 '16 at 11:45
• I compiled and ran your original code, and was very surprised that it worked (probably the compiler being too nice). Compiler's give warnings for a reason, I treat my compiler's warnings like errors and force myself to fix them. I recommend you get to know some of your compiler's flags and do the same in the future. – syb0rg Jun 28 '16 at 13:06

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
}


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.

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.

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.

• I'm eager to see the code... I read the wiki and thought hard of how could the function be, but alas I could only barely think of solution that's complex than I've proposed.. I'm truly eager to see how you could implement this algorithm keeping it more efficient than mine :) – Cherubim Jun 28 '16 at 21:19
• @JS1 We've realised this in the same ~10 seconds ish. I've fixed this. The numbers are not that different though. – SylvainD Jun 29 '16 at 9:57

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.