Improve/fix素数分解函数

Question

我有一个素因数分解函数，但它工作起来很奇怪，我不知道如何让它正确。如果 2 或 3 是重复因子，则应通过 'x' 打印因子并写成 2^(power) 或 3^(power)。

我的输出：2 >> 22^2 | 6 >> 2 x 3^2 | 8 >> 22^22^3 | 9 >> 3 x 3^2.
我该如何更改此代码以使其正常工作。

注意：我在 main() 中声明如果 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);
            }
        }
    }
}

Answer 1

有四个问题：

power 未针对每个因素重置为 0
它正在打印 factor 即使 power 是 0。
在 power 完全确定之前，不应打印 factor 和 power。（目前，每次 power 递增时都会打印代码。
如果第一个因子 > 2，它会在开头打印 x。

修复后的版本如下：

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

有多种方法可以加快速度。

一种加快速度的方法是在因子变得太大时跳过因子（大于 num 的平方根，正如 @chux 在评论），留下 num 作为唯一剩下的因素。可以使用简单的除法而不是计算平方根，如下面的 // speed up 1 代码部分所示：

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

另一种加快速度的方法是在大多数情况下在 for 循环中将 factor 递增 2，除非 factor 为 2，因此序列将为 2 , 3, 5, 7, 9, 11 等:

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

当factor为偶数时，factor += 1 + (factor & 1)将factor加1，当factor为奇数时，factor加2，所以唯一的偶数factor 的值将是初始值 2.

Improve/fix素数分解函数

Improve/fix prime factorization function

c

function

factorization