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 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(di

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.

StackExchange Code Review Q#58244, answer score: 17