Wow that's a big integer! What's its largest prime factor?

Question

I see that there are a few other people who have tackled Project Euler Problem #3. I hope you're not all sick of that question yet. I've not taken a look at those yet (purposely), but am about to now.

I feel like I did a pretty good job on this one, but you tell me. How can I further improve this code? I'm particularly interested in how it could be made even faster, but it seems to already be a pretty quick implementation. My first version took over an hour, this one runs almost instantly. I'm also interested in how I could have used a List<T> instead of an array, if you feel that would have been a better data structure.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Numbers.cs - 79 Lines

There are three functions: IsPrime, IsFactor, and PrimeFactors.

namespace Challenges
{
    public class Numbers
    {
        public static Boolean IsPrime(Int64 number)
        {
            if (number < 2)
            {
                return false;
            }

            if (number == 2)
            {
                return true;
            }

            if (number % 2 == 0)
            {
                return false;
            }

            double sqrtOfNumber = Math.Sqrt(number);

            for (var index = 3; index <= sqrtOfNumber; index += 2) //skip even numbers 
            {
                if (number % index == 0)
                {
                    return false;
                }
            }

            return true;

        }

        public static bool IsFactor(Int64 dividend, Int64 divisor)
        {
            return (dividend % divisor == 0);
        }

        public static Int64[] PrimeFactors(Int64 number)
        {
            Int64[] results = { };

            Int64 maxDivisor = number / 2;
            int index = 0;
            for (Int64 divisor = 2; divisor < maxDivisor; divisor++ )
            {
                if (IsFactor(number,divisor) && IsPrime(divisor))
                {
                    Array.Resize(ref results, results.Length + 1);
                    results[index] = divisor;
                    index++;

                    Int64 factor = number / divisor;
                    if (IsPrime(factor))
                    {
                        Array.Resize(ref results, results.Length + 1);
                        results[index] = factor;
                        break;
                    }
                    else
                    {
                        Int64[] recursiveResults = PrimeFactors(factor);
                        Array.Resize(ref results, results.Length + recursiveResults.Length);
                        for (int i = 0; i < recursiveResults.Length; i++)
                        {
                            results[index] = recursiveResults[i];
                            index++;
                        }
                        break;
                    }
                }
            }

            return results;
        }
    }
}

Console Program

To prove it works, you can check my answer.

namespace Challenges
{
    class ProjectEuler3Program
    {
        static void Main(string[] args)
        {
            const Int64 verybigint = 600851475143;
            Int64[] factors = Numbers.PrimeFactors(verybigint);

            Console.WriteLine((factors.Max()));

            Console.WriteLine();
            Console.WriteLine("Press enter to close...");
            Console.ReadLine();
        }
    }
}

Answer 1

What a fascinating solution! It seems that for every smart decision you made, you also threw in a poor decision or two.

Smart decision: In PrimeFactors(), you start testing divisors from small to large, rather than large to small.

Poor decision: You used if (IsFactor(number,divisor) … rather than while (IsFactor(number,divisor)). Using if instead of while disastrously complicates the program.

Smart decision: In IsPrime(), the index loop skips even numbers. (Why is the variable named index?)

Poor decision: The divisor loop in PrimeFactors() doesn't skip even numbers.

Smart decision: In IsPrime() the index loop goes up to Math.Sqrt(number).

Poor decision: In PrimeFactors(), the divisor loop goes all the way up to number / 2.

Smart decision: You defined an IsFactor() function for readability, and used it in PrimeFactors().

Poor decision: You didn't use IsFactor() in IsPrime().

Smart decision: In PrimeFactors(), whenever you find a successful divisor, you continue the calculation based on factor = number / divisor rather than number.

Poor decision: You continue to factor factor by recursion instead of looping. Worse, the way you used recursion requires you to append the results to the results array.

Poor decision: In the innermost if-else of PrimeFactors()…

if (IsPrime(factor))
{
    …
} else {
    Int64[] recursiveResults = PrimeFactors(factor);
    …
}

the call to PrimeFactors() repeats a lot of throwaway work that was done by IsPrime().

Overall, though, the fundamental issue is the if-vs.-while distinction. Had you chosen while, then you could…

• enumerate the successful divisors in nondecreasing order. Currently, you keep a list of all prime factors and find its maximum. If you could obtain the divisors in order, then you wouldn't need to bother with keeping a list at all.
• eliminate IsPrime() altogether. Every successful divisor will necessarily be prime since you will have factored out all smaller divisors already.

Answer 2

As you mentioned, a List<T> would be a better option than manually resizing the array.

If you ever find yourself resizing an array, List<T> is almost certainly what you want. When a resize is required, it doubles the size (source) of the backing array, so you're trading some space to save a lot of time. As a bonus, it makes the code more readable.

public static Int64[] PrimeFactors(Int64 number)
{
    var results = new List<Int64>();

    Int64 maxDivisor = number / 2;
    for (Int64 divisor = 2; divisor < maxDivisor; divisor++)
    {
        if (IsFactor(number, divisor) && IsPrime(divisor))
        {
            results.Add(divisor);

            Int64 factor = number / divisor;
            if (IsPrime(factor))
            {
                results.Add(factor);
                break;
            }
            else
            {
                Int64[] recursiveResults = PrimeFactors(factor);
                for (int i = 0; i < recursiveResults.Length; i++)
                {
                    results.Add(recursiveResults[i]);
                }
                break;
            }
        }
    }

    return results.ToArray();
}

I would also invert the condition to reduce nesting.

public static Int64[] PrimeFactors(Int64 number)
{
    var results = new List<Int64>();

    Int64 maxDivisor = number / 2;
    for (Int64 divisor = 2; divisor < maxDivisor; divisor++)
    {
        if (!(IsFactor(number, divisor) && IsPrime(divisor)))
        {
            continue;
        }

        results.Add(divisor);

        Int64 factor = number / divisor;
        if (IsPrime(factor))
        {
            results.Add(factor);
            break;
        }
        else
        {
            Int64[] recursiveResults = PrimeFactors(factor);
            for (int i = 0; i < recursiveResults.Length; i++)
            {
                results.Add(recursiveResults[i]);
            }
            break;
        }
    }

    return results.ToArray();
}

Let's move the break out of the conditional

public static Int64[] PrimeFactors(Int64 number)
{
    var results = new List<Int64>();

    Int64 maxDivisor = number / 2;
    for (Int64 divisor = 2; divisor < maxDivisor; divisor++)
    {
        if (!(IsFactor(number, divisor) && IsPrime(divisor)))
        {
            continue;
        }

        results.Add(divisor);

        Int64 factor = number / divisor;
        if (IsPrime(factor))
        {
            results.Add(factor);
        }
        else
        {
            Int64[] recursiveResults = PrimeFactors(factor);
            for (int i = 0; i < recursiveResults.Length; i++)
            {
                results.Add(recursiveResults[i]);
            }
        }

        break;
    }

    return results.ToArray();
}

List<T> has a nice method AddRange:

public static Int64[] PrimeFactors(Int64 number)
{
    var results = new List<Int64>();

    Int64 maxDivisor = number / 2;
    for (Int64 divisor = 2; divisor < maxDivisor; divisor++)
    {
        if (!(IsFactor(number, divisor) && IsPrime(divisor)))
        {
            continue;
        }

        results.Add(divisor);

        Int64 factor = number / divisor;
        if (IsPrime(factor))
        {
            results.Add(factor);
        }
        else
        {
            results.AddRange(PrimeFactors(factor));
        }

        break;
    }

    return results.ToArray();
}

Now if you want to get fancy, you could write the method as an iterator:

public static IEnumerable<Int64> PrimeFactors(Int64 number)
{
    Int64 maxDivisor = number / 2;
    for (Int64 divisor = 2; divisor < maxDivisor; divisor++ )
    {
        if (!(IsFactor(number, divisor) && IsPrime(divisor)))
        {
            continue;
        }

        yield return divisor;

        Int64 factor = number / divisor;
        if (IsPrime(factor))
        {
            yield return factor;
        }
        else
        {
            foreach (var primeFactor in PrimeFactors(factor))
            {
                yield return primeFactor;
            }
        }

        break;
    }
}

Also your Numbers class, as it stands, can be made static.

Answer 3

• This block of code in IsPrime can be simplified by combining conditions that return false.

      if (number < 2)
      {
          return false;
      }
  
      if (number == 2)
      {
          return true;
      }
  
      if (number % 2 == 0)
      {
          return false;
      }
  

• It becomes:

      if (number == 2)
      {
          return true;
      }
  
      if ((number < 2) || (number % 2 == 0))
      {
          return false;
      }
  

• In IsPrime I used Boolean in IsFactor I used bool. It's a nitpick, but consistency is key.

• In lieu of using a list, I should have at least allocated a few array slots, and double the size of the array when it's out of space, rather than resizing the array so frequently. Although, that's exactly how List is implemented, so just use a list.

   public void Add(T item) {
        if (_size == _items.Length) EnsureCapacity(_size + 1);
        _items[_size++] = item;
        _version++;
    }

   private void EnsureCapacity(int min) {
        if (_items.Length < min) {
            int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
            // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
            // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
            if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
            if (newCapacity < min) newCapacity = min;
            Capacity = newCapacity;
        }
    }