Project Euler - Problem 3 in C#

Largest prime factor

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

To find the largest prime factor of a number x, we can do it in couple of ways. One way is the start dividing the number x by y = 2, 3, 4 ... For each factor y of x, this will remove all the smaller factors before moving to the next y till y is less then x. This will work but there is room for improvement over here.

Let improve this existing solution with some facts.

• 2 is the only even prime number, so we can eliminate all the even numbers by recursively dividing the number by 2. Then we can find the prime factor of new whole number faster by incrementing divisor by 2 starting from 3.
• If we don't find the prime factor of x until y (number we are testing to be prime factorial starting from 3) is less then equal to square root of x, means we have a tested all the possible options and no more factors are present. 

Here is the function to find the largest prime factor of a given number.

public static long LargestPrimeFactorByDividingBy2InLoopsInitially(long number)
{
    // set the initial dividing number
    long dividingNumber = 2;
    // looping to divide with only even prime number to remove all possible even numbers
    while (number % 2 == 0)
    {
        number = number / 2;
    }
    // no even number is left, hence starting with 3
    dividingNumber = 3;
    // divide in loops until dividing number is less then square root of expected lpf
    while (System.Math.Sqrt(number) > dividingNumber)
    {
        if (number % dividingNumber == 0)
        {
            // if expected lpf is divisible, update the number
            number = number / dividingNumber;
        }
        else
        {
            dividingNumber += 2;
        }
    }

    return number;
}

Link to Problem #2
Link to Problem #4

If you have any better and faster way, please share it with us. Till then, enjoy solving problems .....