10
\$\begingroup\$

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;
    }

}
\$\endgroup\$
  • \$\begingroup\$ You say you wanted to solve it using OOP, but you haven't used any OOP principles. This is just plain old procedural code. \$\endgroup\$ – sara Jun 26 '16 at 13:18
  • 1
    \$\begingroup\$ Your statement in the comments that the largest prime factor of a number is less than or equal to its square root is obviously wrong. Begin with 2. The largest prime factor of 2 is 2, and it is plainly larger than the square root of 2, so this is not true for the smallest prime. What about the smallest composite? Plainly 3 is bigger than the square root of 6. The principle you actually are trying to use here is a composite number has at least one prime factor smaller than or equal to its square root. \$\endgroup\$ – Eric Lippert Jun 26 '16 at 13:32
  • \$\begingroup\$ Or, put another way: if you cannot find a prime factor smaller than or equal to a number's square root, then the number must itself be prime. \$\endgroup\$ – Eric Lippert Jun 26 '16 at 13:33
  • \$\begingroup\$ To prove this: suppose a number n is composite and the smallest prime factor p is larger than its square root s. Let p be that factor and let q = n / p. q has a prime factor greater than or equal to p, because if it did not, then n would be divisible by a prime smaller than p, but p is the smallest. Therefore q is greater than or equal to p, and therefore also greater than s. Since q and p are both greater than s, then q * p = n is greater than s * s = n. Therefore n > n, which is plainly nonsense. We have our contradiction; p must not exist. \$\endgroup\$ – Eric Lippert Jun 26 '16 at 13:38
  • 3
    \$\begingroup\$ @EricLippert That's a bug report, so it shouldn't be a comment. Could you please convert it to an answer? \$\endgroup\$ – 200_success Jun 26 '16 at 13:44
14
\$\begingroup\$

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;
    }

}
\$\endgroup\$
  • 1
    \$\begingroup\$ Properties are not meant to compute things that are not trivial. If you require 3 loops, 1 of which is nested in another, then I'd say a property is the wrong way to go. They're meant to be cheap and fast, but you're accepting args of type long which could take years to compute. \$\endgroup\$ – sara Jun 26 '16 at 13:17
  • \$\begingroup\$ @kai Reverted to GetAnswer() then. Thanks. \$\endgroup\$ – 200_success Jun 26 '16 at 13:41
  • \$\begingroup\$ @200_success that's a very nice solution, I did have one question: I notice your factor loop iterates by 2, which would include some non-prime numbers such as 9, 15, 21, etc. is it the case that the overhead for testing for those is negligible compared to a primality test? \$\endgroup\$ – Phrancis Jun 26 '16 at 18:36
  • \$\begingroup\$ @Phrancis It's much less work to try dividing by a candidate factor than to test for primality. \$\endgroup\$ – 200_success Jun 26 '16 at 18:50
10
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • \$\begingroup\$ out of curiosity, have you done rigorous testing that the bitshift trick is actually faster than moding with 2? it seems just like the sort of thing that the compiler would do anyway, where a "clever hack" would rather just confuse the optimizer and make it slower overall, but if it's actually measurably faster then I guess it is. \$\endgroup\$ – sara Jun 27 '16 at 7:12
  • \$\begingroup\$ I've done it before and yes, the results were arguably in the favour of the bitwise-manipulation. \$\endgroup\$ – 410_Gone Jun 27 '16 at 7:19
  • \$\begingroup\$ I just did some testing. Using a BigInteger with & was twice as slow as %2, however n.IsEven was twice as fast as %2. using a long switches these numbers completely. Using a long with & was 8-9x faster than %2. %2 on a long performance the same as n.IsEven on a BigInteger. Conclusion, the 'hack' using & on a long is WAY faster. \$\endgroup\$ – Mixxiphoid Jun 27 '16 at 11:42
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ With large values of n, you have teeny tiny inefficiencies (that are hard to detect) since cand is an int and is repeatedly being cast to double when comparing to Math.Sqrt(n) as well as cast to long when used in expressions with n. You should set cand to a long and also calculate the Sqrt and cast it to a long before the first for loop. For large n, this could save you a 100 million implicit casts thereby boosting performance. I do appreciate the brevity of your solution. \$\endgroup\$ – Rick Davin Jul 10 '16 at 15:24
  • \$\begingroup\$ ah, you are very much correct! I guess since factors will be yielded in an ordered way one could also say that the largest prime factor of n is PrimeFactorsOf(n).Last(). although this is still fast enough to factorize any long value pretty much instantly I think. it'd matter if you need to factorize a lot of numbers though! but then again, at this point, why are you handrolling your own algorithm? ;) \$\endgroup\$ – sara Jul 10 '16 at 17:55
4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

  1. 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.

  1. 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.
  2. 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.
  3. Also, if you haven't yet, consider reading about Sieve of Eratosthenes, this is simple and elegant stuff.
\$\endgroup\$
  • \$\begingroup\$ I had originally tried to solve it with the Sieve of Eratosthenes, but the algorithm was so slow for numbers in the hundreds of billions (left it running 12+ minutes and still didn't complete!) that I decided to find a different algorithm. Thanks for your answer! \$\endgroup\$ – Phrancis Jun 27 '16 at 22:25
  • \$\begingroup\$ The Sieve is good for finding many prime numbers below a threshold. It is not so good for finding the factors of a specific number. How large of a sieve would you need, and how exactly would it be used in the solution to this problem? \$\endgroup\$ – 200_success Jun 27 '16 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.