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.
