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

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

• Although each part of your code works, you are missing a much simpler approach; rather than creating a list of all prime factors and returning the largest, look for the largest first (hint: if x = y * z, what values of z maximise y?) and return it straight away. – jonrsharpe Jul 28 '14 at 7:49
• I wonder why didn't you use something like quadratic sieve algorythm? Or at least (if we only talk about 32-b numbers) Pollard's P+1? – Vladislav Qulin Jul 28 '14 at 8:54
• 1. Because it's project Euler, where you are supposed to write your own code, and I wonder if you can just whip out the code for these algorithms yourself. 2. Because the number is tiny and by the time you finished your code the OP has got his result a hundred times over. – gnasher729 Jul 28 '14 at 11:34
• Alternative comment: @VladislavQulin, why don't you post an answer with the source code of the quadratic sieve algorythm (which my spelling checker desperately wants to change to algorithm), or Pollards' P+1? – gnasher729 Jul 28 '14 at 11:36

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.
• Based on these ideas, you should be able to implement a LargestPrimeFactor(Int64 n) function in well under 20 lines, with no helper functions. – 200_success Jul 28 '14 at 8:52
• I don't understand why using recursion was a poor decision. It felt really smart when I figured out that it allowed me to get both of the factors instead of just throwing away the work done by the IsFactor && IsPrime line. I have no idea how the recursion could have been done in a loop instead. – RubberDuck Jul 28 '14 at 10:55
• Also, where else would I stop other than 1/2? For example, the LPF of 15 = (3,5). 5 is > Sqrt(15) and < 0.5 * 15. – RubberDuck Jul 28 '14 at 11:16
• @ckuhn203 One reason not to use recursion is that C# doesn't have tail call optimization, which means for an integer with many factors, you could end up with a stack overflow. Most recursive calls can be converted to loops. I have confidence you can convert this one. – Kris Harper Jul 28 '14 at 14:08
• Perhaps it would be easier to reveal my solution. – 200_success Jul 28 '14 at 15:04

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))
{

Int64 factor = number / divisor;
if (IsPrime(factor))
{
break;
}
else
{
Int64[] recursiveResults = PrimeFactors(factor);
for (int i = 0; i < recursiveResults.Length; 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;
}

Int64 factor = number / divisor;
if (IsPrime(factor))
{
break;
}
else
{
Int64[] recursiveResults = PrimeFactors(factor);
for (int i = 0; i < recursiveResults.Length; 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;
}

Int64 factor = number / divisor;
if (IsPrime(factor))
{
}
else
{
Int64[] recursiveResults = PrimeFactors(factor);
for (int i = 0; i < recursiveResults.Length; 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;
}

Int64 factor = number / divisor;
if (IsPrime(factor))
{
}
else
{
}

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.

• The list really does clean it up. I figured it would, but my head is still a bit stuck in array land. Thank you very much for the example. Reversing the conditional and using continue was a slick trick too. – RubberDuck Jul 28 '14 at 5:18
• 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;
}
}