Decompose a number to product of prime numbers and print it like 18=2*3^2

Question

i have to make a program which decompose numbers into primes and prints it like 18=2*3^2

#include <stdio.h>
void decompose(int n);
unsigned checkprime(int i);

int main() {
    printf("100=");
    decompose(100);
    printf("1\n");
    return 0;
}

void decompose(int n) {
    int i;
    for (i=2; n>1; ++i) {
        if (checkprime(i) == 1 && n%i == 0) {
           n /= i;
           printf("%d*", i);
           i=1;
        }
    }
}

unsigned checkprime(int i) {
   if (i==1)
      return 0;
    for (int j=2; j<=i/2; j++) {
        if (i%j == 0)
            return 0;
    }
    return 1;
}

I can't figure out any way to print it in the right manner

18 is not a prime number. You can not decompose a prime number.:) — Vlad from Moscow, Aug 16 '19 at 09:47
The function checkprime is invalid. It returns true for the number 1 and for example for the number 4.:) — Vlad from Moscow, Aug 16 '19 at 09:49
Possible duplicate of [Decomposition of number into prime numbers](https://stackoverflow.com/questions/7755771/decomposition-of-number-into-prime-numbers) — Christina Jacob, Aug 16 '19 at 09:52
Optimisation: `j `j * j <= i`, taking steps to avoid overflow. — Bathsheba, Aug 16 '19 at 09:55
@eftimo I advice to close this question and at first to ask another question: how to determine whether a number is prime.:) — Vlad from Moscow, Aug 16 '19 at 09:55
For printing, use a flag initialized to false. When you find a prime factor, print a `*` only if the flag is true, then set the flag to true. Finally, print the factor. The result is that you will only print `*` between the factors. — Ian Abbott, Aug 16 '19 at 09:56
@Bathsheba Can use `j <= i / j` to avoid overflow, although division is generally slower than multiplication. Alternatively, calculate the integer square root of `i` first. — Ian Abbott, Aug 16 '19 at 10:00
Instead of printing, the `factorise()` function could put the factors into an array, and return the number of found prime factors. The caller could use this array to print the factors (or find squares, etc) — joop, Aug 16 '19 at 10:02
Find the prime factors in ascending order. For each prime factor, count how many times it occurs. Print the prime factor. Then, if it occurs more than once, print the exponent. Then continue to the next higher prime factor until done. — Tom Karzes, Aug 16 '19 at 10:11

Vlad from Moscow · Accepted Answer · 2019-08-16T11:48:44.873

We, beginners, should help each other.:)

Here you are.

#include <stdio.h>

void decompose( unsigned int n )
{
    const unsigned int FIRST_PRIME = 2;

    printf( "%u = ", n );

    if ( n < FIRST_PRIME )
    {
        printf( "%u\n", n );
    }

    unsigned int m = FIRST_PRIME;

    while ( n > 1 )
    {
        unsigned int i = 0;

        while ( n % m == 0 )
        {
            ++i;
            n /= m;
        }

        if ( i != 0 )
        {
            printf( "%u", m );
            if ( i != 1 )
            {
                printf( "^%u", i );
            }

            if ( n != 1 ) putchar( '*' );
        }

        m = m == FIRST_PRIME ? 3 : m + 2;
    }
}


int main(void) 
{
    while ( 1 )
    {
        printf( "Enter a non-negative number (0 - exit): " );

        unsigned int n;

        if ( scanf( "%u", &n ) != 1 || n == 0 ) break;

        putchar( '\n' );
        decompose( n );
        putchar( '\n' );
    }

    return 0;
}

The program output might look the following way

Enter a non-negative number (0 - exit): 1

1 = 1

Enter a non-negative number (0 - exit): 2

2 = 2

Enter a non-negative number (0 - exit): 3

3 = 3

Enter a non-negative number (0 - exit): 4

4 = 2^2

Enter a non-negative number (0 - exit): 5

5 = 5

Enter a non-negative number (0 - exit): 6

6 = 2*3

Enter a non-negative number (0 - exit): 7

7 = 7

Enter a non-negative number (0 - exit): 8

8 = 2^3

Enter a non-negative number (0 - exit): 9

9 = 3^2

Enter a non-negative number (0 - exit): 10

10 = 2*5

Enter a non-negative number (0 - exit): 11

11 = 11

Enter a non-negative number (0 - exit): 12

12 = 2^2*3

Enter a non-negative number (0 - exit): 13

13 = 13

Enter a non-negative number (0 - exit): 14

14 = 2*7

Enter a non-negative number (0 - exit): 15

15 = 3*5

Enter a non-negative number (0 - exit): 16

16 = 2^4

Enter a non-negative number (0 - exit): 17

17 = 17

Enter a non-negative number (0 - exit): 18

18 = 2*3^2

Enter a non-negative number (0 - exit): 19

19 = 19

Enter a non-negative number (0 - exit): 20

20 = 2^2*5

Enter a non-negative number (0 - exit): 0

As for your code then for example even the function checkprime is invalid. It returns 1 at least for the numbers 1 and 4 but these numbers are not primes.:)

unsigned checkprime (int i){

    for (int j=2;j<i/2;j++) {
        if(i%j==0)
        return 0;
    }
  return 1;
}

score 0 · Answer 2 · answered Aug 16 '19 at 12:10

I suggest you these two optimizations in your decompose function:

void decompose(int n) {
    int first = 1;  // check if first prime factor

    while (n % 2 == 0) {
        n /= 2;
        if (first) {
            first = 0;
            printf("2");
        } else {
            printf("*2");
        }
    }
    // here, n must be odd

    int s = sqrt(n); // 1st optimization: https://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-prime-number-to-determine-if-it-is-pr
    for (int i = 3; i <= s;) {
        if (checkprime(i) && n % i == 0) {
            n /= i;
            if (first) {
                first = 0;
                printf("%d", i);
            } else {
                printf("*%d", i);
            }
        } else {
             i += 2; // 2nd optimization: n must be odd
        }
    }
}

Decompose a number to product of prime numbers and print it like 18=2*3^2

2 Answers2