c-改进/修正素数分解函数

Question

我有一个函数素数分解，但它工作得很糟糕，我不知道如何使它正确。如果2或3是收获因子，则应通过"x"打印因子，并像2^(幂)或3^(幂(幂))一样书写。

MyOutput：2>gt；22^2|6>gt；2 x 3^2|8>gt；22^22^3|9>gt；3 x 3^2。
如何更改此代码以使其正常工作。

注意：我在main()中说过，如果num==1：打印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

有四个问题：

1. power没有为每个因子重置为0
2. 即使power为0，它也在打印factor
3. 在完全确定power之前，不应打印factor和power。(目前，每次power递增时，都会打印代码
4. 如果第一个因子是>2

以下固定版本：

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将CCD_18递增2，因此factor的唯一偶数值将是初始值2。