# Finding the prime factors of a positive number

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

• 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. Jun 14, 2016 at 23:58
• @Edward I have updated the question and fixed the bug. I have also removed my_sqrt, my_printnbr and my_putchar functions. Jun 16, 2016 at 13:08

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.