Why am I getting negative outputs when I run my method to print prime factors of a user input?

Question

So, I'm writing a method that takes a user input and prints all of its prime factors. It works, except it's giving me a negative number at the end of every list. What is causing this??

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

When I input 90, I get 1, 2, 3, 5, -3. When I input 31, I get 1, 31, -1. When I input 500, the output is 1, 2, 5, 10, -5. You get the point.

I know my code is not complete in terms of filtering ONLY prime factors, but I want to address these negative numbers before refining things to make sure only prime numbers get on the list.

Answer 1

The main problem is due to numeric overflow. In particular, your code doesn't have an appropriate exit condition, such as checking if counter > input, in your loop code of

    for(int counter = 1; input >= 1; )
    {
        if(input % counter == 0)
        {
            factors.Add(counter);
            input = input / counter;
            counter++;
        }
        else
        {
            counter++;
        }
        
    }

For positive counter values where input % counter == 0 is true, then counter is less than or equal to input. Thus, the line of code input = input / counter; will have input still be a positive integer, so the for loop check of input >= 1 will always succeed. This means, since counter is a signed 32-bit integer, it'll continue increasing until it reaches Int32.MaxValue = 2147483647, i.e., 2^31 - 1. It then overflows with the high bit set to become the smallest negative integer value which is Int32.MinValue = -2147483648, i.e., -2^31. After that, it'll continue increasing until it gets to the negative of the input value, in which case the line factors.Add(counter); will add this negative value, and input = input / counter; will cause input to become -1, thus finally causing the loop to terminate.

Thus, with your example of 90, the positive factors of 1, 2, 3, 5 multiply to 30, leaving a factor of 90 / 30 = 3 as the input value, which is why the final entry is -3. Similarly, with 31, there's just the factor of 31, so input becomes 1, resulting in a final list value of -1. Finally, with 500, the factors of 1, 2, 5, 10 multiply to 100. Thus, there's a remaining factor of 5, and so a final entry of -5 is in your list.

A relatively simple fix is changing the for loop condition check of input >= 1 to counter <= input instead. Also, although your code is not complete, as you state, one small suggestion is that since the for loop always increments counter, instead of doing that in two separate code lines as you do now, you can remove those lines and add that increment as the increment/decrement part of the for loop, e.g., have that line instead be

    for(int counter = 1; counter <= input; counter++)

---

Regarding your stated goal of finding and reporting on the prime factors, in addition to what I suggest above, there's a relatively simple set of changes you can make to your loop to accomplish this. In particular, just start with counter at 2 (since 1 is not a prime) and insert this line

            while (input % counter == 0)

above this line

                 input = input / counter;

This works because the first time the if condition works, counter will be the smallest prime factor of input. Then the while loop will remove all instances of that prime factor. Thus, each next value of counter which is a factor can't be composite since each of the counter prime factors would have been removed earlier. Thus, the code will only be finding and adding prime factors to the factors list.

Below is some sample code

        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 counter is less than equal to the input, if input mod counter is equal to 0,
            // add counter to factor list and then, as long as input mod counter is 0,
            // set input value to input / counter.
            
            for(int counter = 2; counter <= input; counter++)
            {
                if(input % counter == 0)
                {
                    factors.Add(counter);
                    while (input % counter == 0)
                        input = input / counter;
                }
            }
            
            // display the prime factors 

            Console.Write("Prime factors of {0}: ", userInput);
            foreach (int factor in factors)
            {
                Console.Write("{0}  ", factor);
            }
            Console.WriteLine();
        }

        static void Main(string[] args)
        {
            int[] testUserInput = {90, 31, 500};
            for (int i = 0; i < testUserInput.Length; i++)
            {
                PrimeFactors(testUserInput[i]);
            }
        }

which produces the output of

Prime factors of 90: 2  3  5
Prime factors of 31: 31
Prime factors of 500: 2  5

Answer 2

the problem come from this line:

if(input % counter == 0)

if input = 31 and counter >= 32 => input % counter always not equal 0. The counter increase until it gets overflow and flipped to the minimum number. For instance:

int a = int.MaxValue;
int b = 1;
int c = a + b; // c will be -2147483648

Answer 3

Please, note that largest possible prime for userInput factor is Sqrt(userInput):

userInput = p * p

Knowing this fact we can implement

using System.Collections.Generic;

...

private static IEnumerable<int> DistinctPrimeFactors(int value) {
  if (value <= 1)
    yield break;

  // Special case for even numbers
  if (value % 2 == 0) {
    yield return 2; 

    while (value % 2 == 0)
      value /= 2;
  }

  int n = (int) (Math.Sqrt(value) + 0.5);

  for (int divisor = 3; divisor <= n; divisor += 2)   
    if (value % divisor == 0) {
      yield return divisor;

      do
        value /= divisor;
      while (value % divisor == 0);

      n = (int) (Math.Sqrt(value) + 0.5); 
    }

  if (value > 1) 
    yield return value;
}

Then you can Join the prime factors:

Console.Write(string.Join(" ", DistinctPrimeFactors(500)));

Output: (500 == 2 * 2 * 5 * 5 * 5)

2 5

Fiddle