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