Skip to main content
added 2 characters in body
Source Link
Phrancis
  • 20.5k
  • 6
  • 69
  • 155

Basically, we and"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.

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.

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.

added 13 characters in body
Source Link
Phrancis
  • 20.5k
  • 6
  • 69
  • 155
private bool IsPrime(BigInteger n)
// Based on Wikipedia page for "Primality test"
// https://en.wikipedia.org/wiki/Primality_test#Simple_methods
{
private bool IsPrime(BigInteger n)
// Based on Wikipedia page for "Primality test"
// https://en.wikipedia.org/wiki/Primality_test#Simple_methods
{
else if (  (n != 5 && n % 5 == 0))
else if (  (n != 5 && n % 5 == 0))
if (maxPrimeFactor % 2 == 0) { maxPrimeFactor += 1; }
if (maxPrimeFactor % 2 == 0) { maxPrimeFactor += 1; }

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

for (long i = maxPrimeFactor; i >= 1; i = i - 2)
for (long i = maxPrimeFactor; i >= 1; i = i - 2)
private bool IsPrime(BigInteger n)
// Based on Wikipedia page for "Primality test"
// https://en.wikipedia.org/wiki/Primality_test#Simple_methods
{
else if (  (n != 5 && n % 5 == 0))
if (maxPrimeFactor % 2 == 0) { maxPrimeFactor += 1; }

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

for (long i = maxPrimeFactor; i >= 1; i = i - 2)
private bool IsPrime(BigInteger n)
// Based on Wikipedia page for "Primality test"
// https://en.wikipedia.org/wiki/Primality_test#Simple_methods
{
else if (  (n != 5 && n % 5 == 0))
if (maxPrimeFactor % 2 == 0) { maxPrimeFactor += 1; }

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

for (long i = maxPrimeFactor; i >= 1; i = i - 2)
Source Link
Der Kommissar
  • 20.3k
  • 4
  • 70
  • 158

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 let's 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;
    }
}