1
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Your code is broken. The variable i is not initialized before it is used as an index in a for loop. \$\endgroup\$ – pacmaninbw Jun 28 '16 at 11:45
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – syb0rg Jun 28 '16 at 13:06
7
\$\begingroup\$
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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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 :) \$\endgroup\$ – Cherubim Jun 28 '16 at 21:19
  • 1
    \$\begingroup\$ @JS1 We've realised this in the same ~10 seconds ish. I've fixed this. The numbers are not that different though. \$\endgroup\$ – Josay Jun 29 '16 at 9:57
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.