3
\$\begingroup\$

I have an assignment to write on the standard output the prime factors of a positive number displayed in ascending order and separated by '*'. My code works, but I need help reviewing it before I submit my work. Allowed functions: write, printf, atoi.

void    find_factors(int n)
{
    int i;
    int separated;

    i = 3;
    separated = 0;
    if (n <= 1)
        return ;
    while (n % 2 == 0)
    {
        if (separated)
            printf("*");
       printf("%d", 2);
       separated = 1;
        n = n / 2;
    }
    while (i <= n)
    {
        while(n % i == 0)
        {
            if (separated)
                printf("*");
            printf("%d", i);
            separated = 1;
            n = n / i;
        }
        i += 2;
    }
    if (n > 2)
    {
      if (separated)
            printf("*");
      printf("%d", n);
    }
}
\$\endgroup\$
  • \$\begingroup\$ It doesn't seem to quite work. find_factors(72); prints 2*2*2**3*3. Please test more, fix the bug and then update the question. \$\endgroup\$ – Edward Jun 14 '16 at 23:58
  • \$\begingroup\$ @Edward I have updated the question and fixed the bug. I have also removed my_sqrt, my_printnbr and my_putchar functions. \$\endgroup\$ – Junius L. Jun 16 '16 at 13:08
4
\$\begingroup\$

1) The reasons for 2 loops while (n % 2 == 0) and while (i <= n) is to optimize division by 2 and allow the next prime candidate to be found with += 2.

As printing is a sink-hole of time, these small savings could be ignored and code changed to one loop.

int i = 2;
while (i <= n) {
   while(n % i == 0) {
      ...
      printf("%d", i);
      separated = 1;
      n = n / i;
   }
   i += i==2 ? 1 : 2;
}

2) Negative numbers are a problem and not well supported here, nor do they need to be. Recommend unsigned than int.

3) As an alternative to a flag and repeated test code for the "*", perhaps

char *separator = "";
...
while (...) {
   printf("%s%d", separator, 2);
   separator = "*";
   ...
}

4) Code fails for the following. OP did say "prime factors of a positive number", so 0 and negative numbers are excusable to some degree.

  find_factors(INT_MAX);  // infinite loop
  find_factors(1);        // no output
  find_factors(0);        // infinite loop
  find_factors(negative)  // no output

5) Initialize at the same time as declaration.

// int i;
// int separated;
// i = 3;
// separated = 0;
int i = 3;
int separated = 0;

6) Consider bool for boolean variables

#include <stdbool.h>
// int separated = 0;
bool separated = false;

7) Wavy formatting

    if (separated)
        printf("*");
   printf("%d", 2);
   separated = 1;
    n = n / 2;

8) Careful passing a string to printf() as a format string as it might someday contain %.

// printf("*");
fputs("*", stdout);
// or 
fputc('*', stdout);
//
putchar('*');

// OP did say  "write, printf, atoi.", so could use the following, which is a bit pedantic.
printf("%s", "*");  

9) Efficiency. For large values of n, code does n/2 loops. Better to terminate at about the sqrt(n). At n % i time, also calculate qu = n / i. This can often be had for free, depending on the processor. Once i>qu, code is done.

\$\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.