Find the largest Prime Factor of the number 600851475143

Question

I am trying to complete this challenge, which is to find the Find the largest Prime Factor of the number 600851475143.

My current solution is below:

static void Main(string[] args)
{
    const long targetNumber = 600851475143;
    var primeFactors = new List<long>();

    for (long i = 1; i <= targetNumber; i++)
    {
        if(PrimeFactor(targetNumber, i))
        {
            primeFactors.Add(i);
        }
    }

    var biggestPrimeFactor = primeFactors.Max();

    Console.WriteLine(biggestPrimeFactor);
    Console.ReadLine();
}

public static bool PrimeFactor(long number, long i)
{
    return number % i == 0;
}

My main problem is that this is taking ages to run, but it's also not very eloquent.

How can I improve on the above?

Thanks

Answer 1

I'd look into Max() function. Keeping track of the largest prime you have found so far might be better instead of using Max()?

Also how is the PrimeFactor function returning the largest prime factor? It looks like its only returning the divisor, not necessarily a prime number.

If your goal is to only return the largest prime factor, why don't you start counting from the targetNumber down to 0?

Answer 2

Note 2 things.

1. There is at most 1 prime, bigger then sqrt(n)

2. If p1 is prime factor, then either p1 is max prime factor, or you can divide by p1, without affecting largest factor. So all in all, it gives you code.

   static void Main(string[] args)
   
   {
       const long targetNumber = 600851475143;
       var primeFactors = new List<long>();
   
       for (long i = 1; i*i <= targetNumber; i++)
       {
           while(PrimeFactor(targetNumber, i))
           {
               primeFactors.Add(i);
               targetNumber /= i;
           }
       }
   
       primeFactors.Add(targetNumber);
       var biggestPrimeFactor = primeFactors.Max();
   
       Console.WriteLine(biggestPrimeFactor);
       Console.ReadLine();
   }
   

Answer 3

Gotta love Linq...

This would need to be tweaked to make it generic enough to use for any number (ie the Enumerable.Range only accepts ints) but it really shows off the power of Linq. This brings back the answer in .036 seconds on my machine.

void Main()
{
    const double targetNumber = 600851475143; 
    var biggestPrimeFactor = Enumerable.Range(2, Convert.ToInt32(Math.Sqrt(targetNumber)))
                                       .Reverse()
                                       .AsParallel()
                                       .Where(g => targetNumber % g == 0 && IsPrime(g))
                                       .FirstOrDefault();

    Console.WriteLine(biggestPrimeFactor); 
}

private static bool IsPrime(int number)
{
    for (int index = 2; index <= Math.Sqrt(number); index++)
        if (number % index == 0) return false;
    return true;
}

Answer 4

Easier solution:

static void Main(string[] args)
    {
        ulong n = 600851475143;
        ulong i = 1;
        ulong result;
        while (n != 1)
        {
            i++;
            how = 0;
            while (n % i == 0)
            {
                n /= i;
            }
        }
        result = i;
        Console.WriteLine(result);
    }

Answer 5

A few things about finding primes.

1. Prebuild in the single digit primes 2, 3, 5, & 7 (and put into step 4 if used)
2. The only numbers you need to check end with 1, 3, 7, or 9 (assuming you start after step 1)
3. For a stage 1 increase in speed, use independent parallel checking by assigned range
4. For a stage 2 increase, use a caching system to get the feed of the most up-to-date prime number list. When a prime number is found, feed it into the caching system.
5. Bridge to pure C for the heavy lifting.

Item 2 = 60% reduction in numerical checks. Just use the base numbers and multiply them by 10 for each check. (17, 27, 37, 47, etc.)

Item 3 = utilization of multiple cores, possibly multiple separate computers. You can utilize .net's parallel.foreach() for ease of use.

Item 4 = in your example, you consider it a "list" of primes found. but each thread will need to lock/unlock access. It is better for each thread to pull in the list and use it as a primer for the next check if you are using parallel prime # checking.

Item 5 = removing as much .net and windows overhead as possible.

Since you are trying to get to the largest prime given the ceiling you provided, just check backwards for each 1, 3, 7, or 9. You'll probably find it within a few seconds-minutes.

Answer 6

Rather than checking every number to see which are divisors of your target, start by finding the prime factors of the target and then simply return the largest.

The fundamental rule of arithmetic tells us that the target has a single set of prime factors. We can infer that for the target T, T = p x V where p is the first prime factor found and V is the product of all remaining factors.

What this means is that you should loop through known prime numbers, dividing the target by each prime that is a factor. Keep doing this until the target is reduced to one - and the last prime number used as a divisor is the largest.

Thus

while workingTarget > 1

    if workingTarget % knownPrime = 0
        workingTarget = workingTarget / knownPrime
    else
        next knownPrime