I have a function prime factorization, but it works wierdly and I have no idea how to make it right. It's expected to print factors through 'x' and write like 2^(power) or 3^(power) if 2's or 3's are reapeating factors.

MyOutput: 2 >> 22^2 | 6 >> 2 x 3^2 | 8 >> 22^22^3 | 9 >> 3 x 3^2.
How do I change this code to make it work properly.

Note: I have stated in main() that if num == 1: print 1.

void prime_factors(int num)
{
    int power = 0;

    for (int factor = 2; num > 1;   factor)
    {
        while (num % factor == 0)
        {
            if (factor >= 3 && power >= 1)
                printf(" x %d", factor);
            else
                printf("%d", factor);
            num /= factor;
              power;
            if (power >= 1)
            {
                printf("^%d", power);
            }
        }
    }
}

CodePudding user response：

There are four problems:

1. power is not being reset to 0 for each factor
2. It is printing factor even if power is 0.
3. It should not print the factor and power until power has been fully determined. (Currently, the code is printing every time power is incremented.
4. It prints x at the beginning if the first factor is > 2.

Fixed version below:

void prime_factors(int num)
{
    int power = 0;
    int first = 1;

    for (int factor = 2; num > 1;   factor)
    {
        power = 0;
        while (num % factor == 0)
        {
            num /= factor;
              power;
        }
        if (power >= 1)
        {
            if (first)
                printf("%d", factor);
            else
                printf(" x %d", factor);
            printf("^%d", power);
            first = 0;
        }
    }
}

There are various ways to speed it up.

One way to speed it up is to skip factors when they get too large (larger than the square root of num, as suggested by @chux in the comments), leaving num as the only remaining factor. Rather than calculating the square root, a simple division can be used, as shown in the // speed up 1 code section below:

void prime_factors(int num)
{
    int power = 0;
    int first = 1;

    for (int factor = 2; num > 1;   factor)
    {
        power = 0;
        // speed up 1
        if (num / factor < factor)
        {
            // skip impossible factors
            factor = num;
        }
        // end of speed up 1
        while (num % factor == 0)
        {
            num /= factor;
              power;
        }
        if (power >= 1)
        {
            if (first)
                printf("%d", factor);
            else
                printf(" x %d", factor);
            printf("^%d", power);
            first = 0;
        }
    }
}

Another way to speed it up is to increment factor by 2 in the for loop most of the time, except when factor is 2, so the sequence will be 2, 3, 5, 7, 9, 11, etc.:

    for (int factor = 2; num > 1; factor  = 1   (factor & 1))

The factor = 1 (factor & 1) increments factor by 1 when factor is even, and increments factor by 2 when factor is odd, so the only even value of factor will be the initial value 2.