Problem 3: Largest prime factor

Problem:

Please find the problem here.

Solution:

Again, brute force is going to work for this, just try different prime numbers and try. Note that $ 600851475143 > 2^{39} $, 32 bit integer will not work for the problem, we will need 64 bit integer.
C# compiler will give an error right away like this.

namespace Problem003
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using Common;

    class Program
    {
        static void Main(string[] args)
        {
            int x = 600851475143;
        }
    }
}

Error 1 Cannot implicitly convert type 'long' to 'int'. An explicit conversion exists (are you missing a cast?)

A nice feature of C# to avoid error. With that, all I have to do is to do trial division. Here is the code to do that:

namespace Problem003
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using Common;

    class Program
    {
        static void Main(string[] args)
        {
            long x = 600851475143;
            while (x != 1)
            {
                long d = 0;
                for (long c = 2; c < x; c++)
                {
                    if (x % c == 0)
                    {
                        d = c;
                        // Found a factor!
                        Console.WriteLine(d);
                        break;
                    }
                }
                if (d != 0)
                {
                    x = x / d;
                    
                }
                else
                {
                    // No factor found - this must be another prime factor
                    Console.WriteLine(x);
                    break;
                }
            }
        }
    }
}

This is run very quick - this tell us one basic principle with problem solving - be optimistic. Suppose we were pessimistic to believe the prime factor is going to be large, this is going to loop for long period of time and we spent time thinking about more advanced algorithm, which we really don't need.

Even if it does turn out to be bad, we can try something else soon. Trying this one doesn't hurt since it is really quick to code this up.

In fact, I myself learn a lesson here, since I coded the complicated one to start with. I used Pollard's rho algorithm to do the factoring. Here is the implementation of it.

public static int CommonFactor(int m, int n)
{
    while (true)
    {
        int r = m % n;
        if (r == 0)
        {
            return n;
        }

        m = n;
        n = r;
    }
}

// Pollard's rho algorithm for factoring (note that it does not factor 2^n)
public static List<long> PollardFactor(long n)
{
    List<long> factors = new List<long>();
    while (true)
    {
        // Factor it
        long x = 2;
        long y = 2;
        long d = 1;
        while (d == 1)
        {
            x = PollardSequence(x);
            y = PollardSequence(PollardSequence(y));
            long diff = x - y;
            if (diff < 0)
            {
                diff = -diff;
            }
            d = CommonFactor(diff, n);
            if (d == n)
            {
                factors.Add(n);
                break;
            }
        }
        if (d == n) { break; }
        factors.Add(d);
        n = n / d;
    }

    return factors;
}

private static long PollardSequence(long x)
{
    return (x % int.MaxValue) * (x % int.MaxValue) + 1;
}

The implementation is really just implementing the pseudocode on the wiki so it is trivial. It runs in more or less the same time as the brute force as they both are done without a blink. I learn the factoring algorithm there, and I hope you would go learn that too.

Answer: 6857