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 { ListfactorsList = 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.