• 1

• 20.5k
• 6
• 69
• 155

Largest Prime Factor (PE3) inusing OOP style

• 20.5k
• 6
• 69
• 155

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?

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