How to express integer as a product of its prime factors?

Viewed 596
//Determine the prime factors of a number
for(i = 2; i <= num; i++) {             //Loop to check the factors.
    while(num % i == 0) {               //While the input is divisible to "i" which is initially 2.
        printf("%d ", i);               //Print the factor.
        num = num / i;                  //Divide the num by "i" which is initially 2 to change the value of num.
        }
    }

I know that this is the way of finding the prime factors of a number using for loop. But I don't know how to express the output integer as a product of its prime factors. For example, INPUT IS: 10 || OUTPUT IS: 2 x 5 = 10. How do we do this? TIA.

3 Answers

You should:

  • Save the original value.
  • Print the operator x between each prime factors.
  • Print the original value at the end.
#include <stdio.h>

int main(void) {
    int num;
    int i;
    int start_num;
    int is_first = 1;
    if(scanf("%d", &num) != 1) return 1;
    start_num = num;                        //Save the original value.

    //Determine the prime factors of a number
    for(i = 2; i <= num; i++) {             //Loop to check the factors.
        while(num % i == 0) {               //While the input is divisible to "i" which is initially 2.
            if(!is_first) printf("x ");     //Print the operator before second and later operands.
            printf("%d ", i);               //Print the factor.
            num = num / i;                  //Divide the num by "i" which is initially 2 to change the value of num.
            is_first = 0;                   //Mark that there is already one or more operand.
        }
    }
    printf("= %d\n", start_num);            //Print the original value.
    return 0;
}

I've revised the code to give something that's a bit more robust than what I posted previously, as well as being slightly more efficient. Again I assume you want (unsigned) 32-bit input via stdin in the range: [1, 2^32 - 1]

As far as the algorithm is concerned, it should be apparent that searching for factors need only test candidates up to floor(sqrt(num)). There are also factors with multiplicity, e.g., (24) => {2, 2, 2, 3}.

Furthermore, after factoring out (2), only odd factors need to be tested.

For a 32-bit (unsigned) type, there will be fewer than (32) prime factors. This gives a simple upper-bound for a fixed-size array for storing the successive prime factors. The prime factors in the array are in ascending order, by virtue of the algorithm used.


/******************************************************************************/

#include <stdio.h>


int main (void)
{
    /* print a value in [1, 2^32 - 1] as a product of primes: */

    unsigned long int n, u, prime[32];
    int np = 0;

    if (scanf("%lu", & n) != 1 ||
        ((n == 0) || ((n & 0xffffffffUL) != n)))
    {
        fprintf(stderr, "factor < u32 = 1 .. 2^32 - 1 >\n");
        return (1);
    }

    if (n == 1) /* trivial case: */
    {
        fprintf(stdout, "1 = 1\n");
        return (0);
    }

    u = n; /* (u) = working value for (n) */

    for (; (u & 0x1) == 0; u >>= 1) /* while (u) even: */
        prime[np++] = (2);

    while (u > 1)
    {
        unsigned long q, d = 3, c = 0; /* (c)omposite */

        if (np != 0) /* start at previous odd (prime) factor: */
            d = (prime[np - 1] == 2) ? (3) : prime[np - 1];

        for (; (c == 0) && (q = u / d) >= d; )
        {
            if ((c = (q * d == u)) == 0) /* not a factor: */
                d += 2;
        }

        prime[np++] = (d = (c == 0) ? u : d);

        u /= d; /* if (u) is prime, ((u /= d) == 1) (done) */
    }

    for (int i = 0; i < np; i++)
    {
        const char *fmt = (i < np - 1) ? ("%lu x ") : ("%lu = ");
        fprintf(stdout, fmt, prime[i]);
    }

    fprintf(stdout, "%lu\n", n);

    return (0);
}

/******************************************************************************/

You can output the factors with the appropriate punctuation:

// Output the prime factors of a number
void factorize(int num) {
    int n = num;                         // save the initial value of num
    const char *sep = "";                // initial separator is an empty string
    for (int i = 2; i <= num / i; i++) { // stop when num is reduced to a prime
        while (num % i == 0) {           // while the input is divisible to "i"
            num = num / i;               // divide the num by "i" (remove the factor)
            printf("%s%d", sep, i);      // print the separator and the factor.
            sep = " x ";                 // change the separator for any further factors
        }
    }
    if (num > 1 || n <= 1) {
        printf("%s%d", sep, num);          // print the last or single factor.
    }
    printf(" = %d\n", n);                // print the rest of the equation
}
Related