Problem #5 and my huge blunder

I started working on problem 5 and it took about 20 minutes. I was quite happy with my solution, but as soon as I read the first reply in the solution thread I immediately realized what a big dumbass I am. This is what happens when you don't see what the problem is really asking and you don't put a lot of thought into it. My solution is definitely the opposite of elegant and is not worthy of posting.

 

Problem #5

 

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

 

Now really think about this problem and what it is asking you. You might at first think: hey, lets create a for-loop that iterates from 2 to 20 and checks the divisibility! Return true if it is evenly divisible by all of them. Now let's create a while-loop that stops when we find a number that returns true.

 

Let me stop you right there.

 

Long ago, or maybe last semester in discrete math, you learn about something called the Least Common Multiple. I'll show you the definition right out of my textbook:

Least Common Multiple: The least common multiple of the positive integers a and b is the smallest positive integer that is divisible by both a and b. The least common multiple exists because the set of integers divisible by both a and b is nonempty, and every nonempty set of positive integers has a least element.

 

What we do is take the LCM of 1 - 20, better written as LCM(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... , 20). What we do is find the prime factors of every number and take the largest power of each. Then you muliply all those together and, voila, you have your answer.

 

LCM(1, ... , 20) = 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19

 

You can even check it out on wolfram alpha if you'd like: www.wolframalpha.com/input/

 

It now boils down to creating a method that finds the LCM of a set of integers. At least I learned a great deal about problem solving with this problem.

Comments

Prime factorization is a

Prime factorization is a beautiful thing. Actually, I think that's got to be the single most interesting thing to me from the discrete math course. It's like, every number is part of a huge lattice structure built atop primes.

 

What algorithm did you use for finding the lcm?

Thanks for your response! I

Thanks for your response!

I haven't actually written one yet. I've done a little code but it is not completed. I think finding the highest power is probably the biggest problem.

 

I'd definitely agree with you about the prime factorization being the most interesting from discrete. Especially the proof. It is so simple and elegant, yet it has such far reaching consequences. Number theory in general is just a beautiful subject, hands down.