编写PrimeFactors方法打印质因数时输出负数的原因排查

我编写了一个名为PrimeFactors的C#方法，接收用户输入的整数并打印其质因数。方法可运行，但每次输出的列表末尾都会出现负数：输入90时输出1, 2, 3, 5, -3；输入31时输出1, 31, -1；输入500时输出1, 2, 5, 10, -5。我知道代码尚未实现仅过滤质数的逻辑，但希望先解决负数输出问题。相关代码如下：

static void PrimeFactors(int userInput)
{
    // create a variable which is a new version of userInput that can be manipulated by the method
    int input = userInput;
   
    // declare a new list which will contain all of the factors of the user input. 
    var factors = new List<int>();


    // While the input is greater than 1, if input mod counter is equal to 0,
    // add counter to factor list and set input value to input / counter
    // if input % counter != 0, break and start the for loop again
    
    for(int counter = 1; input >= 1; )
    {
        if(input % counter == 0)
        {
            factors.Add(counter);
            input = input / counter;
            counter++;
        }
        else
        {
            counter++;
        }
        
    }
    // display the prime factors 
    foreach (int factor in factors)
    {
        Console.Write($"{factor}  ");
    }
}

负数出现的原因 #

循环条件input >= 1存在漏洞：当input被分解到1之后，循环仍会继续执行。此时counter会不断递增，直到超出int类型的最大值发生溢出，变成负数。当counter为负数时，会满足input % counter == 0（比如1 % -1 == 0、3 % -3 == 0），导致负数被加入列表，随后input被除以负数变成负数，循环才终止。

修复方案 #

1. 修改循环终止条件：把input >= 1改为input > 1，当input被分解到1时直接终止循环，避免counter无限递增溢出为负数。
2. 优化因数查找逻辑：原代码中找到因数后立即counter++会漏掉重复的质因数（比如分解12时会漏掉第二个2），因此找到能整除的因数时不要递增counter，只有当当前counter无法整除input时再递增。同时可以把counter的初始值从1改为2，因为1不是质数，无需加入质因数列表。

修复后的代码 #

static void PrimeFactors(int userInput)
{
    int input = userInput;
    var factors = new List<int>();

    // 循环条件改为input > 1，避免input为1时继续循环导致counter溢出
    // counter从2开始，跳过非质数的1
    for(int counter = 2; input > 1; )
    {
        if(input % counter == 0)
        {
            factors.Add(counter);
            input = input / counter;
            // 找到因数后不递增counter，确保能重复提取相同的质因数
        }
        else
        {
            counter++;
        }
    }

    foreach (int factor in factors)
    {
        Console.Write($"{factor}  ");
    }
}

内容的提问来源于stack exchange，提问作者Hash Slinging Slasher