Prime factoring function using recursion

Question

As a programming exercise, I decided to make a prime factoring function using recursion:

    static bool isPrime(int n)
    {
        if (n < 2)
            return false;
        if (n % 2 == 0)
            return (n == 2);
        int root = (int)Math.Sqrt((double)n);
        for (int i = 3; i <= root; i += 2)
            if (n % i == 0) return false;
        return true;
    }

    static bool iseven(int n)
    {
        return n % 2 == 0;
    }

    static int[] prfact(int n, int curr, List<int> nums)
    {
        if (nums.All(x => isPrime(x)) && isPrime(curr))
        {
            nums.Add(curr);
            return nums.ToArray();
        }
        else if (iseven(curr))
        {
            nums.Add(2);
            return prfact(n, curr / 2, nums);
        }
        else if (!iseven(curr))
        {
            int div = 3;
            while (curr % div != 0 || !isPrime(div))
                div += 2;

            nums.Add(div);
            return prfact(n, curr / div, nums);
        }
        else
            return null;
    }

    static int[] factor(int n)
    {
        return prfact(n, n, new List<int>());
    }

How efficient is it and how can it be improved?

Answer 1

• +1 for stopping your isPrime search at the SqRt(n). That's a nice little optimization.
• +1 for incrementing by 2. It's nice to see you realized that since it wasn't possibly even by this point, that you could optimize.
• Next, consider a sieve or memento implementation for further performance improvements on isPrime.
• Consider renaming root to limit.
• +1 for extracting an isEven method.
• -1 for neglecting to use it in your isPrime method.
• Instead of having prfact and factor, Rename prfact to factor, overloading the latter. Make it private scoped to hide the implementation details from the outside world.

---

Sorry for the mostly non-algo review. Not my strong suit & short on time.

Answer 2

The algorithm recomputes primes from 3 upwards over and over again, even though it is guaranteed that smaller factors has already been eliminated at the previous recursion steps.

Instead, start a factor finding loop from the last entry in nums. Notice that the first factor found is guaranteed to be prime. So not only it speeds up the search, but also renders isPrime unnecessary.

I also recommend to extract the factor finding loop into a method.

Answer 3

Although you have accepted an answer I have a couple of things to add:

1. The function can't handle values lesser than 2, and it shouldn't as it has no meaning. But instead of returning properly it ends in a long while loop.
2. Instead of int you could use ulong because it signals the domain of the function.

3. There is no need to return anything from the prfact() because the nums argument holds the result.

4. You can optimize the algorithm in that the curr argument is unnecessary as shown below.

Version without curr argument

public static void GetPrimeFactors(ulong value, List<ulong> factors)
{
  if (value <= 1)
    return;
  else if (value % 2 == 0)
  {
    factors.Add(2);
    value /= 2;
  }
  else
  {
    ulong div = 3;

    while (value % div != 0 || !isPrime(div))
    {
      div += 2;
    }

    factors.Add(div);
    value /= div;

  }

  GetPrimeFactors(value, factors);
}

public static IList<ulong> GetPrimeFactors(ulong value)
{
  var factors = new List<ulong>();
  GetPrimeFactors(value, factors);
  return factors;
}