Saturday, February 28, 2015

Project Euler - Largest prime factor


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

https://projecteuler.net/problem=3

public class LargestPrimeFactor
    {
        List factorsList = new List();
        bool isPrime = true;
         
        public long FactorNumber(long number)
        {
            double sqroot = Math.Sqrt(number);
            for (long i = 1; i < sqroot; i++)
            {
                if (number % i == 0) 
                {
                    for (long j = 2; j < i; j++)
                    {
                        if (i % j == 0) 
                        {
                            isPrime = false;
                            break;
                        } 
                    }

                    if (isPrime == true) 
                    {
                        factorsList.Add(i);

                        bool secondaryIsPrime = true;
                        for (int k = 2; k < (number / i); k++)
                        {
                            if ((number / i) % k == 0) 
                            {
                                secondaryIsPrime = false;
                                break;                            
                            } 
                        }
                        if (secondaryIsPrime == true) factorsList.Add(number / i);
                        secondaryIsPrime = true;
                    } 
                    isPrime = true;
                } 
            }

            factorsList.Sort();
            long[] factorsArray = factorsList.ToArray();
            return factorsArray[factorsArray.Length - 1];
        }
    }

My comments: So, this was a very interesting problem to do. Solving the problem for small numbers took me about 2 minutes. HOWEVER, realizing that my computer was brute forcing it and trying to deal with the larger number and NOT coming to a solution withing a reasonable time (10+ mins is about when I gave up on waiting) made me realize I needed to change how it was working. By making it iterate fewer times the brute force gives a "instant" answer if you only have to iterate up to the square root of the number in question. So for example, let's say we have a number 64. The square root is 8. So we can iterate only up to 8 and find out that 1, 2, 4, and 8 are the only factors.. and we can get the other side of the factor by diving the number (64) over those 4 values. So we know that 1 goes with 64, 2 goes with 32, 4 goes with 16, and 8 goes with 8.. and then from there we can only take the ones of those that are prime. As opposed to just iterating from 1 to n, which takes a very very long time and is extremely inefficient.