Onwards, to Project Euler problem #3. The problem is defined as below:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

So, basically, we need to find out which factors make up a certain number. The easiest way to do this is simply by trial division. A very naïve implementation would be something like this:

function Get-PrimeFactors ([long]$number)
{
    while ($number -gt 1)
    {
        for($i = 2; $i -le $number; $i++)
        {
            if($number % $i -eq 0)
            {
                $number = $number / $i;
                $i;
                break;
            }
        }
    }
}

To be honest, for a number of this magnitude even the simplest of solutions will work. I’ve been looking at different integer factorization algorithms (using my trusty pal Wikipedia), but none of them is simple enough to actually fit the problem. Most of them are actually really suitable for the problem, if the number was much, much bigger.

However, there are a few optimizations to be made. For instance, we can assume that we only have to check for divisors up to the square root of the number in question, because anything higher than that has a pairing divisor which is lower than the root. For instance, let’s look at 42. $\sqrt{42} \approx 6.5$, so we only have to check up to (and including) 6. If we look at all possible solutions for $a \times b = 42$, we’ll see that none of them have two factors above 6:

• $2 \times 21$
• $3 \times 14$
• $7 \times 6$
• $6 \times 7$
• $14 \times 3$
• $21 \times 2$

Besides that, we need to only look for prime factors. We know that all primes (except for the first one, being ‘2’) are odd. Adding all of these optimizations in, we’ll get something like this:

function Get-PrimeFactors ([long]$number)
{
        while($number % 2 -eq 0)
        {
            2;
            $number /= 2;
        }
        for($i = 3; $i -le [Math]::Sqrt($number); $i+= 2)
        {
            while($number % $i -eq 0)
            {
                $number /= $i;
                $i;
            }
        }
        $number
}

This is more or less a good enough solution for this problem. Using the number from the problem description, it will run take around 50ms to get all factors of that integer.

As I’ve said, I’ve looked into a bunch of factorization algorithms, but they were all pretty much overkill for the problem at hand. As you see, the solution is found in 50ms. Even bigger numbers like 600851475143123, which is the product of two quite substantial primes, takes less than 30 seconds. I think this function might be useful for later Project Euler problems, so I’ll keep it in the library for now.