Largest Prime Factor (PE3) using OOP

Question

I want to learn some C# syntax/paradigms (I'm more used to Java), and have been wanting to get a bit better at math as well, so I solved ProjectEuler3: Largest prime factor with the following small program in LINQPad. It gives the correct answer and completes in 0.05s-0.08s.

For reference, here is the problem statement:

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

What is the largest prime factor of the number 600851475143 ?

All feedback welcomed. In particular, are there some C# mistakes I am making or features I am missing on due to being very new at it?

I'm also not that great at math at the moment, if you know of edge cases that I may have missed with the calculations below, please let me know so I can improve my math knowledge a bit as well!

_{P.S.: Note the BigNumbersUtils.Sqrt extension method comes from this Stack Overflow answer. I am excluding it since it is not my code. it gives the same result as Math.Sqrt but for BigInteger type.}

void Main()
{
    Console.WriteLine("ProjectEuler3: Largest prime factor");
    BigInteger testCase = 600851475143;
    ProjectEuler3 PE3 = new ProjectEuler3(testCase);
    Console.WriteLine("Prime factor of {0} is: {1}", testCase, PE3.GetAnswer());
}

class ProjectEuler3
{
    private BigInteger number;

    public ProjectEuler3(BigInteger number)
    {
        this.number = number;
    }

    public BigInteger GetAnswer()
    {
        // largest possible prime factor of a number is its square root [citation needed]
        BigInteger maxPrimeFactor = BigNumbersUtils.Sqrt(number);
        // make sure number we start from is odd, as even numbers are never going to be prime
        if (maxPrimeFactor % 2 == 0) { maxPrimeFactor += 1; }
        // iterating by 2s to skip even numbers
        for (BigInteger i = maxPrimeFactor; i >= 1; i = i - 2)
        {
            if (IsFactor(i, number) && IsPrime(i))
            {
                return i;
            }
        }
        return 1;
    }

    private bool IsFactor(BigInteger n, BigInteger factorOf)
    {
        return (factorOf % n == 0) ? true : false;
    }

    private bool IsPrime(BigInteger n)
    // Based on Wikipedia page for "Primality test"
    // https://en.wikipedia.org/wiki/Primality_test#Simple_methods
    {
        // short-circuit very common numbers
        if (n <= 1)
        {
            return false;
        }
        else if (n <= 3) 
        {
            return true;
        }   
        else if (n % 2 == 0 || n % 3 ==0)
        {
            return false;
        }
        else if (  (n != 5 && n % 5 == 0))
        {
            return false;
        }
        // iterate with trial division
        BigInteger i = 5;
        while (i * i <= n)
        {
            if (n % i == 0 || n % (i + 2) == 0)
            {
                return false;
            }
            i++;
        }
        return true;
    }

}

Answer 1

Project Euler questions are primarily about math. This isn't really the place to practice object-oriented programming. In fact, trying to model the problem literally will lead you to a suboptimal solution.

The "right" algorithm is very simple, and involves no primality testing.

I wouldn't bother with an IsFactor() method at all — if you just write it as a modulo test, there is no confusion about the order the parameters.

class ProjectEuler3
{
    private long number;

    public ProjectEuler3(long number)
    {
        this.number = number;
    }

    public long GetAnswer()
    {
        long n = this.number;
        while (n % 2 == 0)
        {
            n /= 2;
        }
        for (long factor = 3; factor < n; factor += 2)
        {
            while (n % factor == 0)
            {
                n /= factor;
            }
        }
        return n;
    }

}

Answer 2

There's no need for BigInteger here, long will suffice. It's a more natively supported type, and should perform faster. (Citation needed?)

You can then use Math.Sqrt which almost certainly will be faster.

Making these two changes has allowed the execution of mine to be 0.025s in LINQPad.

---

Don't structure method headers and comments like so:

private bool IsPrime(BigInteger n)
// Based on Wikipedia page for "Primality test"
// https://en.wikipedia.org/wiki/Primality_test#Simple_methods
{

Place the comments above the method header itself, or in the method. Don't break the header and the first brace up like that.

---

The IsFactor method does not need the ternary, it's just noise at that point.

private bool IsFactor(long n, long factorOf)
{
    return factorOf % n == 0;
}

(Down to 0.019s at this point.)

---

You have an excessive number of parenthesis on this if:

else if (  (n != 5 && n % 5 == 0))

---

While the modulo operator is quick, it can be just a bit quicker by using a neat boolean trick:

else if ((n & 0x01) == 0 || n % 3 == 0)

Basically, we "and" n and 0x01, which will strip all bits except the last. If the result is 0, then it was even. Otherwise, it's odd.

(Down to 0.018s.)

We could do the same on this line:

if (maxPrimeFactor % 2 == 0) { maxPrimeFactor += 1; }

But there's no speed to be gained here, that line is only ever executed once.

---

C#6.0 lets you do a nice little trick (which actually decreases execution time further), and use an expression-bodied member:

private bool IsFactor(long n, long factorOf) => factorOf % n == 0;

Down to 0.017s.

---

This is a really awkward way to write this for loop:

for (long i = maxPrimeFactor; i >= 1; i = i - 2)

I was wondering what i = i - 2 was doing there, as it's more simply written as i -= 2:

for (long i = maxPrimeFactor; i >= 1; i -= 2)

---

All these adjustments (and some minor whitespace cleanup) lead us to:

void Main()
{
    Console.WriteLine("ProjectEuler3: Largest prime factor");
    var testCase = 600851475143;
    var PE3 = new ProjectEuler3(testCase);
    Console.WriteLine("Prime factor of {0} is: {1}", testCase, PE3.GetAnswer());
}

class ProjectEuler3
{
    private long number;

    public ProjectEuler3(long number)
    {
        this.number = number;
    }

    public long GetAnswer()
    {
        // largest possible prime factor of a number is its square root [citation needed]
        var maxPrimeFactor = (long)Math.Sqrt(number);

        // make sure number we start from is odd, as even numbers are never going to be prime
        if ((maxPrimeFactor & 0x01) == 0)
        {
            maxPrimeFactor++;
        }

        // iterating by 2s to skip even numbers
        for (long i = maxPrimeFactor; i >= 1; i -= 2)
        {
            if (IsFactor(i, number) && IsPrime(i))
            {
                return i;
            }
        }

        return 1;
    }

    private bool IsFactor(long n, long factorOf) => factorOf % n == 0;

    // Based on Wikipedia page for "Primality test"
    // https://en.wikipedia.org/wiki/Primality_test#Simple_methods
    private bool IsPrime(long n)
    {
        // short-circuit very common numbers
        if (n <= 1)
        {
            return false;
        }
        else if (n <= 3) 
        {
            return true;
        } 
        else if ((n & 0x01) == 0 || n % 3 == 0)
        {
            return false;
        }
        else if (n != 5 && n % 5 == 0)
        {
            return false;
        }

        // iterate with trial division
        long i = 5;
        while (i * i <= n)
        {
            if (n % i == 0 || n % (i + 2) == 0)
            {
                return false;
            }
            i++;
        }

        return true;
    }
}

Answer 3

The thing that bothers me most about your code (and most of the answers) is that they are really long and verbose. I'd probably roll with something like the following:

public class Euler3
{
    public static long LargestPrimeFactorOf(long n)
    {
        return PrimeFactorsOf(n).Max();
    }

    private static IEnumerable<long> PrimeFactorsOf(long n)
    {
        for (var cand = 2; cand <= Math.Sqrt(n); cand++)
            for (; n % cand == 0; n /= cand)
                yield return cand;

        if (n > 1) yield return n;
    }
}

It has the "benefit" of being lazy in it's factorization method (which may or may not be a good thing, in this case it doesn't add much since we need to iterate over all factors to find the largest). I also find it to be more consice and declarative.

I also see no need whatsoever to make these instance methods since they are pure mathematical functions who depend only on their input. You spoke of OOP, but this is not a problem that is suited for OOP code. It's too small scale. We are designing an algorithm, we're not buildinga complex system.

Answer 4

For such small numbers, you are overwhelmingly more likely to find small factors by counting up from 2 in fewer steps than finding the largest factor counting down (which you will find before the largest prime factor, in general). Consider that every factor greater than the square root has a cofactor less than the square root, so the density of factors is much lower among the integers greater than the square root. You really should start at two and count up. Every time you find a factor, since the number has no smaller factors, you know the factor you found was prime. (This makes your IsPrime() superfluous.) It's traditional to divide this prime out of your number and continue testing the same (and then larger) trial factors from the reduced number. (You test the same prime again because one of its powers may divide the original number.)

Since you're now counting up, you can skip about one third of the candidate factors you would check in your current code. Other that 2 and 3 all prime numbers are congruent to 1 and 5 modulo 6. Consequently, you would test the list

2,3,5,
+2=7,+4=11,
+2=13,+4=17,
+2=19,+4=23,
+2=25, ...  // which shows that you are going to hit some composites in your trial factors

where the increments continue alternating between +2 and +4. Unroll your loop (once) to do both of these per pass.

Why does this work? Consider:

• If i is congruent to 0 modulo 6, then i is divisible by 2 and 3, so you have already tested for divisibility by all the factors of i.
• If i is congruent to 2 modulo 6, then i is divisible by 2.
• If i is congruent to 3 modulo 6, i is divisible by 3.
• If i is congruent to 4 modulo 6, i is divisible by 2.

No similar statement holds if i is congruent to 1 or 5 modulo 6. So as long as you have checked for divisibility y 2 and 3 and you count up instead of down, you know that no new information can be revealed by is that are not congruent to 1 or 5 modulo 6.

Of one wants to unroll a little more and skip about 20% of the remaining candidate factors, one tests 2, 3, and 5, and then only

1, 7, 11, 13, 17, 19, 23, and 29 modulo 30

since every other remainder shares a factor of 2, 3, or 5 with 30.

Answer 5

More nitpicking:

1. Instead of making a console app you could make a unit test project. So every test you just send a number to the function and assert the returned result. Like this:

   [TestMethod]
   public void FindsLargestPrimeFactor()
   {
       var number = 42;
       var expected = 7;
   
       var actual = ProjectEuler3.FindLargestPrimeFactor(number);
   
       Assert.AreEqual(expected, actual);
   }
   

ProjectEuler3 here is considered to be a static class. So you can treat it like a small library.

2. Here:

   // make sure number we start from is odd ...
   if (maxPrimeFactor % 2 == 0) { maxPrimeFactor += 1; }
   

you should decrease maxPrimeFactor instead of increasing. Though, as others said, all the iterating algorighm should be conceptually rewritten.

3. Do remember that 1 is neither prime nor composite, thus in any case in can't be returned from a function that is finding primes.
4. If you desperately want to check some common cases in the IsPrime method, I would recommend to extract this logic to a separate private static method naming in something like CheckSmallNumbers or CheckTrivialCases.
5. Also, if you haven't yet, consider reading about Sieve of Eratosthenes, this is simple and elegant stuff.