I am trying to solve the Project Euler problem #5, "What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?"
To solve this I created methods to find the LCM (Lowest Common Multiple) using the GCD (Greatest Common Divisor)
Using the LCM method I find the LCM of the first and second prime number, then use the result of that method to find the LCM of the result and third prime number, etc, etc
static void Main(string[] args)
{
int listLength = 20;
Boolean[] listOfNumbers = new Boolean[listLength];
ArrayList listOfPrimes = new ArrayList();
for (int iii = 0; iii < listLength; iii++)
{
listOfNumbers[iii] = true;
}
for (int iii = 2; iii < listLength; iii++)
{
if (listOfNumbers[iii])
{
for (int jjj = iii * 2; jjj < listLength; jjj = jjj + iii)
{
listOfNumbers[jjj] = false;
}
listOfPrimes.Add(iii);
}
}
int lcm = 1;
for (int iii = 0; iii < listOfPrimes.Count; iii++)
{
lcm = LCM(lcm, (int)listOfPrimes[iii]);
}
}
static public int GCD(int a, int b)
{
int division;
int modulus;
if (a < b)
{
int c = b;
b = a;
a = c;
}
division = a / b;
modulus = a % b;
if (modulus == 0)
{
return b;
} else
{
return GCD(division, modulus);
}
}
static public int LCM(int a, int b)
{
int lcm = (a * b) / GCD(a, b);
return lcm;
}
The actual answer is meant to be 232792560 but I get 22044 when using only the prime numbers for the LCM but 51731680 when using all 20 numbers for the LCM
Obviously neither answer was the correct one, I am just wondering am I on the right track or have I messed something up? If possible just looking a poke in the right direction
It isn't just primes, but their factorizations. Consider: what's the LCM of 2, 3, 4? If you just use primes, you get 2 * 3 = 6, which is clearly not a multiple of 4. What you want is the LCM of 2, 3, 2 * 2. Once you have the three numbers broken up that way, you can ignore 2, because it's obviously a factor of 2 * 2.
To extend this:
Since you just asked for a poke in the right direction, I leave the coding of this up to you. :)