Project Euler #3 solution

Question

I'm trying to solve Project Euler problem #3, which asks:

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

Can you please review the code and suggests improvements?

namespace FullPractice
{
  public class PrimeFactorFinder
  {
    private readonly HashSet<int> _myPrimeFactors = new HashSet<int>();
    private long _myNumber;

    public void PrimeFactors(long number)
    {
        _myNumber = number;
        FindPrimeFactors();
        DisplayAllPrimeFactors();
        ShowLargestPrimeFactor();
    }

    private void ShowLargestPrimeFactor()
    {
        Console.WriteLine("\nLargest Prime Factor = {0}",_myPrimeFactors.Last());
    }

    private void FindPrimeFactors()
    {
        long temp = _myNumber;
        int primeNumber = 2;
        while (temp != 1)
        {
            if (temp%primeNumber == 0)
            {
                _myPrimeFactors.Add(primeNumber);
                temp = temp/primeNumber;
            }
            else
            {
                primeNumber = GetPrimeNumberAfter(primeNumber);
            }
        }
    }

    private void DisplayAllPrimeFactors()
    {
        Console.WriteLine("All prime factors of {0} are : ", _myNumber);
        foreach (var primeFactor in _myPrimeFactors)
        {
            Console.Write("{0},", primeFactor);
        }
    }

    private int GetPrimeNumberAfter(int primeNumber)
    {
        var next = primeNumber + 1;
        while (true)
        {
            if (IsPrime(next))
            {
                return next;
            }
            next++;
        }
    }


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

Answer 1

PrimeFactors why do you do output there? It would be much better if you return an IEnumerable<long> with all the prime factors of the number passed as input. Let the client decide what it needs to do with the result. It might need to output it but it might need to do something with all the prime factors instead.

Why do you create an object for that class? It should not hold any state. What you need is a static method. It should be something purely functional. static IEnumerable<long> PrimeFactors(long number). With your code, the client of your code has to instantiate a new PrimeFactors instance, which is useless.

Holding the state also causes it to produce wrong results in cases such as the following:

var primeFactorFinder = new PrimeFactorFinder();
primeFactorFinder.PrimeFactors (33);
primeFactorFinder.PrimeFactors (5);

which outputs:

All prime factors of 33 are : 
3,11,
Largest Prime Factor = 11
All prime factors of 5 are : 
3,11,5,
Largest Prime Factor = 5

clearly something went wrong because _myPrimeFactors, which should really be local to FindPrimeFactors never got cleared between the first and the second invocation of PrimeFactors.

Your algorithm looks ok. If you need more performances you probably need to trade some memory for a better execution time and adopt a solution based on a Sieve of Eratosthenes-like approach.

Answer 2

• The Project Euler problem asks only for the largest prime factor, so there is no need to create an array of all prime factors of the given number.
• (This is my main argument, and similar to https://codereview.stackexchange.com/a/62029/35991.) There is no need to search/test for prime numbers if you test the possible factors in increasing order and divide the given number by a found factor as much as possible, because each found factor is necessarily a prime number.

This reduces the algorithm to:

using System;
using System.Diagnostics; // for StopWatch

namespace FullPractice
{
  public class PrimeFactorFinder
  {
        public static void Main (string[] args)
        {
            long number = long.Parse(args[0]);
            Stopwatch stopWatch = Stopwatch.StartNew();
            long result = largestPrimeFactorOf(number);
            stopWatch.Stop();
            Console.WriteLine("Largest prime factor: {0} time: {1}ms", result, stopWatch.Elapsed.TotalMilliseconds);
        }

        static long largestPrimeFactorOf(long n)
        {
            long largestFactor = 1;

            // i is a possible *smallest* factor of the (remaining) number n.
            // If i * i > n then n is either 1 or a prime number.
            for (long i = 2; i * i <= n; ++i)
            {
                if (n % i == 0)
                {
                    largestFactor = i;
                    // Divide by the highest possible power of the found factor:
                    while (n > 1 && n % i == 0)
                    {
                        n /= i;
                    }
                }
            }

            if (n > 1)
            {
                // n is a prime number and therefore the largest prime factor of the 
                // original number.
                largestFactor = n;
            }
            return largestFactor;
        }
    }
}

On a MacBook Pro using Mono this computes the largest prime factor of 600851475143 in about 0.4 milliseconds (compared to 6 milliseconds with your code).