is there a way to specify a range in Java without having to loop through the range and check each value? I'm trying to find the smallest number that is evenly divisible by all numbers in the range 1-10. I know I can use ten 'ands' to check if a number is divisible by each number in the range but it just seems messy and longwinded. Anyone have any ideas? Also, please don't give me the answer to this!

Thanks,

Alan

Ivan Jozsef Balazs wrote:Alan Smith wrote:Hi,

Also, please don't give me the answer to this!

I hope not risking to give the answer with the hint on the loop constructions.

I mean the actual answer. I was thinking of using an infinite outer loop to keep scrolling through every number until I find a number that is evenly divisible in the range 1 - 10 by using an inner loop for the 1 - 10.

Alan Smith wrote:I'm trying to find the smallest number that is evenly divisible by all numbers in the range 1-10. I know I can use ten 'ands' to check if a number is divisible by each number in the range but it just seems messy and longwinded. Anyone have any ideas?

Yes: think about factors. If a number is divisible by 10, you already know that it MUST be divisible by 2 and 5 - and what do those two numbers have in common?.

Chew on that for a bit...

BTW, this doesn't really have anything to do with a "range operator".

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Winston Gutkowski wrote:

Yes: think about factors. If a number is divisible by 10, you already know that it MUST be divisible by 2 and 5 - and what do those two numbers have in common?.

Chew on that for a bit...

BTW, this doesn't really have anything to do with a "range operator".

Winston

Hi Winston, I have the solution but its a mess! Basically, I want to refactor the code and am looking for the approach programmatically as opposed to the problem itself. Messy solution:

As you can see, elegence is out the window here but it works!

Alan Smith wrote:Hi Winston, I have the solution but its a mess! Basically, I want to refactor the code and am looking for the approach programmatically as opposed to the problem itself.

I don't understand that last sentence at all. Did you actually

*read*my post?

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Winston Gutkowski wrote:Alan Smith wrote:Hi Winston, I have the solution but its a mess! Basically, I want to refactor the code and am looking for the approach programmatically as opposed to the problem itself.

I don't understand that last sentence at all. Did you actuallyreadmy post?

Winston

Yes Winston, I read your post but my maths is a little loose, I'm going through problems like this to understand maths and logic now that you mention it. I know that what 2 and 5 have in common is that they are both evenly divisible into 10. But I'm genuinely stumped as to what I can do with that, sorry!

Alan Smith wrote:Matthew Brown wrote:

Oh, and you really don't need to checki % 1.

Then I'm lost!

What is

`(1 % 1)`?

`(2 % 1)`?

`(3 % 1)`?

`(34865 % 1)`? Notice a pattern?

Alan Smith wrote:Yes Winston, I read your post but my maths is a little loose...now that you mention it. I know that what 2 and 5 have in common is that they are both evenly divisible into 10. But I'm genuinely stumped as to what I can do with that, sorry!

And what are 2 and 5 divisible by?

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Winston Gutkowski wrote:Alan Smith wrote:Yes Winston, I read your post but my maths is a little loose...now that you mention it. I know that what 2 and 5 have in common is that they are both evenly divisible into 10. But I'm genuinely stumped as to what I can do with that, sorry!

And what are 2 and 5 divisible by?

Winston

Both are divisible by 1.

Alan Smith wrote:Both are divisible by 1.

As Matthew said,

*all*numbers are divisible by 1. What else are 2 and 5 divisible by, and what is the

*difference*between them and 10?

Winston

Articles by Winston can be found here

Winston Gutkowski wrote:Alan Smith wrote:Both are divisible by 1.

As Matthew said,allnumbers are divisible by 1. What else are 2 and 5 divisible by, and what is thedifferencebetween them and 10?

Winston

2 is divisible by itself, 5 is divisible by itself. Difference between 10 and 2 = 8, difference between 10 and 5 = 5.

Alan Smith wrote:2 is divisible by itself, 5 is divisible by itself. Difference between 10 and 2 = 8, difference between 10 and 5 = 5.

You're being too literal: What is

*similar*about 2 and 5, that is

*different*about 10? Hint: if you re-read all the posts so far you should be able to find the answer.

Winston

Articles by Winston can be found here

Winston Gutkowski wrote:Alan Smith wrote:2 is divisible by itself, 5 is divisible by itself. Difference between 10 and 2 = 8, difference between 10 and 5 = 5.

You're being too literal: What issimilarabout 2 and 5, that isdifferentabout 10? Hint: if you re-read all the posts so far you should be able to find the answer.

Winston

I think I get what your saying. If anything is a factor of a number you dont have to check it. ie. if I check a number is divisible by 10, 9, 8, and 7 I should get my answer because the rest of the numbers (below 7) are factors of these numbers. Does that make sense?

Alan Smith wrote:I think I get what your saying. If anything is a factor of a number you dont have to check it. ie. if I check a number is divisible by 10, 9, 8, and 7 I should get my answer because the rest of the numbers (below 7) are factors of these numbers. Does that make sense?

Yup, but

Winston

[Edit] Sorry, the above is incorrect. I should have said: "what

*else*do you need to know to work out when you have your answer?".

Articles by Winston can be found here

Winston Gutkowski wrote:Alan Smith wrote:I think I get what your saying. If anything is a factor of a number you dont have to check it. ie. if I check a number is divisible by 10, 9, 8, and 7 I should get my answer because the rest of the numbers (below 7) are factors of these numbers. Does that make sense?

Yup, but you can also do it another, much easier, way. Hint: what are 2 and 5 (and 3 and 7 in your range) called?

Winston

This is a guess but 2 and 5 are the common divisors, and 3 and 7 are the undivisors (for want of a better word!).

Alan Smith wrote:This is a guess but 2 and 5 are the common divisors, and 3 and 7 are the undivisors (for want of a better word!).

OK, maybe it's best that you look at this page, because I'm clearly not explaining it properly. The fact is that you

*don't*have to check every number in your range, but the ones that you

*do*check are very important.

Winston

Articles by Winston can be found here

Winston Gutkowski wrote:Alan Smith wrote:This is a guess but 2 and 5 are the common divisors, and 3 and 7 are the undivisors (for want of a better word!).

OK, maybe it's best that you look at this page, because I'm clearly not explaining it properly. The fact is that youdon'thave to check every number in your range, but the ones that youdocheck are very important.

Winston

Sorry for wreaking your head, i'll have a look and take it from there. Thanks for your patience.

Alan Smith wrote:Sorry for wreaking your head, i'll have a look and take it from there. Thanks for your patience.

No probs. The fact is that you DON'T have to check every number to work out the smallest number that is divisible by every number from 1-10 - in fact, you only have to deal with the factors 9, 8, 7 and 5 - but I'll leave you to work out why.

Winston

Articles by Winston can be found here

Winston Gutkowski wrote:Alan Smith wrote:Sorry for wreaking your head, i'll have a look and take it from there. Thanks for your patience.

No probs. The fact is that you DON'T have to check every number to work out the smallest number that is divisible by every number from 1-10 - in fact, you only have to deal with the factors 9, 8, 7 and 5 - but I'll leave you to work out why.

Winston

I thought about checking only range [6...10], but your post gave me some doubts... Could you explain please, why checking of 9, 8, 7 and 5 would be enough?

Aleksey Vladimirovich wrote:Could you explain please, why checking of 9, 8, 7 and 5 would be enough?

If 8 is a divisor of a number, then so are its divisors, 2 and 4, as well.

If 9 is a divisor of a number, then so is 3.

If 2 and 3 divide a number, so does 6. Why?

n=2.x (1)

n=3.y (2)

From 3 times (1) 3.n = 6.x (3)

From 2 times (2) 2.n = 6.y (4)

Now subtract (4) from (3):

n = 6x-6y=6.(x-y)

Pretty elementary stuff.

Ivan Jozsef Balazs wrote:Aleksey Vladimirovich wrote:Could you explain please, why checking of 9, 8, 7 and 5 would be enough?

If 8 is a divisor of a number, then so are its divisors, 2 and 4, as well.

If 9 is a divisor of a number, then so is 3.

If 2 and 3 divide a number, so does 6. Why?

n=2.x (1)

n=3.y (2)

From 3 times (1) 3.n = 6.x (3)

From 2 times (2) 2.n = 6.y (4)

Now subtract (4) from (3):

n = 6x-6y=6.(x-y)

Pretty elementary stuff.

I got this, that is why I wrote about [6...10] range. My question was why only those 4 particular numbers? Is there some rule for excluding other numbers? In this particular case it works, but I think it's rather an exception than a rule... One can't create an universal algorithm, if he doesn't have a particular rule. I mean, what if one need to do the same but for [1...30] range. My variant (checking only a second part of given range) will work with any range. That's why I asked why only those particular numbers...

Aleksey Vladimirovich wrote:I got this, that is why I wrote about [6...10] range. My question was why only those 4 particular numbers?

quick note - that is actually FIVE numbers....

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

fred rosenberger wrote:What you are trying to find is the "least common multiple" of the numbers 1 through 10. Google that term, and you will find tons of info. What folks have been hinting at here is that there are two kinds of numbers...someone already mentioned "composite" numbers. If you know (or find out) what the opposite of a composite is, it will help you.

Aleksey Vladimirovich wrote:I got this, that is why I wrote about [6...10] range. My question was why only those 4 particular numbers?

quick note - that is actually FIVE numbers....

You misunderstood me... If you take a look at the chain of posts, you'll notice that this: "My question was why only those 4 particular numbers?" was related to the post of Winston Gutkowski:

Winston Gutkowski wrote:No probs. The fact is that you DON'T have to check every number to work out the smallest number that is divisible by every number from 1-10 - in fact, you only have to deal with the factors 9, 8, 7 and 5 - but I'll leave you to work out why.

Winston

I didn't get how come checking of only

**these**4 numbers (9, 8, 7 and 5) is a sufficient condition...

Aleksey Vladimirovich wrote:You misunderstood me...

sorry.

Aleksey Vladimirovich wrote:

I didn't get how come checking of onlythese4 numbers (9, 8, 7 and 5) is a sufficient condition...

Well...look at one of 'missing' numbers...let's say 2.

can you think of any situation where a potential number would be divisible by all of the four, but NOT divisible by 2? Specifically, if a candidate number is divisible by a certain one of those four, you know it MUST ALSO be divisible by 2. Therefore, if I test my candidate number with 8, I don't need to test with 2.

The trick is to identify the best (i.e. smallest) set of candidate numbers that is also sufficient.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

fred rosenberger wrote:Well...look at one of 'missing' numbers...let's say 2.

No, let's say 6 instead of 2, what in this case? I think it's possible that number would be divisible by 9, 8, 7 and 5, but not by 6 (not in this particular case), what I'm saying is - I don't see any rule in this sequence and asking someone to explain.

I suggest something like that as a solution:

I cannot think of possible algorithm for random range of numbers, basing on some other rule.

Aleksey Vladimirovich wrote:fred rosenberger wrote:Well...look at one of 'missing' numbers...let's say 2.

No, let's say 6 instead of 2, what in this case? I think it's possible that number would be divisible by 9, 8, 7 and 5, but not by 6 (not in this particular case), what I'm saying is - I don't see any rule in this sequence and asking someone to explain.

so take 6. you know that if a number is divisible by 6, it must be divisible by 2. It must also be divisible by 3. In fact, if it is divisible by 2 and 3, you know it MUST be divisible by 6.

Now take that a step further. we know that if your candidate is divisible by 8, it must be divisible by 2.

Please READ the article suggested above - about composite numbers, their opposites, and finding least common multiples. That is all relevant. we didn't post those suggestions just to hear ourselves talk.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Aleksey Vladimirovich wrote:No, let's say 6 instead of 2, what in this case? I think it's possible that number would be divisible by 9, 8, 7 and 5, but not by 6 (not in this particular case), what I'm saying is - I don't see any rule in this sequence and asking someone to explain.

Simply put:

9 = 3 x 3

and

8 = 2 x 2 x 2

so any number that divides by 9 MUST divide by 3, and any number that divides by 8 MUST divide by 2 - ergo any number that divides by both 9 AND 8, must divide by both 3 AND 2; and what numbers divide by both 3 AND 2?

Do you also notice that those numbers 2, 3, 5 and 7 have cropped up again? I refer you to my post about 50 back.

Winston

Articles by Winston can be found here

fred rosenberger wrote:Aleksey Vladimirovich wrote:fred rosenberger wrote:Well...look at one of 'missing' numbers...let's say 2.

No, let's say 6 instead of 2, what in this case? I think it's possible that number would be divisible by 9, 8, 7 and 5, but not by 6 (not in this particular case), what I'm saying is - I don't see any rule in this sequence and asking someone to explain.

so take 6. you know that if a number is divisible by 6, it must be divisible by 2. It must also be divisible by 3. In fact, if it is divisible by 2 and 3, you know it MUST be divisible by 6.

Now take that a step further. we know that if your candidate is divisible by 8, it must be divisible by 2.

Please READ the article suggested above - about composite numbers, their opposites, and finding least common multiples. That is all relevant. we didn't post those suggestions just to hear ourselves talk.

The sufficient condition will be to check only range: [(lowerBorderOfRange < upperBorderOfRange / 2 ? (int) upperBorderOfRange / 2 : lowerBorderOfRange), upperBorderOfRange] and what I wrote in my previous post's code or am I wrong?

Winston Gutkowski wrote:Aleksey Vladimirovich wrote:No, let's say 6 instead of 2, what in this case? I think it's possible that number would be divisible by 9, 8, 7 and 5, but not by 6 (not in this particular case), what I'm saying is - I don't see any rule in this sequence and asking someone to explain.

Simply put:

9 = 3 x 3

and

8 = 2 x 2 x 2

so any number that divides by 9 MUST divide by 3, and any number that divides by 8 MUST divide by 2 - ergo any number that divides by both 9 AND 8, must divide by both 3 AND 2; and what numbers divide by both 3 AND 2?

Do you also notice that those numbers 2, 3, 5 and 7 have cropped up again? I refer you to my post about 50 back.

Winston

Yeah, I see. But I don't think this algorithm would be faster than the one what I was talking about. Or would it?

Aleksey Vladimirovich wrote:Yeah, I see. But I don't think this algorithm would be faster than the one what I was talking about. Or would it?

Much. As I said, quite a while back, and fred has also repeated, you don't need to check

*any*numbers to find the lowest common multiple; you need to check the

*factors*, and you already know what the range for them is. What we've been trying to steer you to, is to determining WHICH factors are relevant; and for the range 1-10 it's 9, 8, 7 and 5.

Now you need to find out why (and I've given you a partial explanation above), but to do it properly you really must look at all the links you've been given.

Winston

Articles by Winston can be found here

Aleksey Vladimirovich wrote:Winston Gutkowski wrote:Aleksey Vladimirovich wrote:No, let's say 6 instead of 2, what in this case? I think it's possible that number would be divisible by 9, 8, 7 and 5, but not by 6 (not in this particular case), what I'm saying is - I don't see any rule in this sequence and asking someone to explain.

Simply put:

9 = 3 x 3

and

8 = 2 x 2 x 2

so any number that divides by 9 MUST divide by 3, and any number that divides by 8 MUST divide by 2 - ergo any number that divides by both 9 AND 8, must divide by both 3 AND 2; and what numbers divide by both 3 AND 2?

Do you also notice that those numbers 2, 3, 5 and 7 have cropped up again? I refer you to my post about 50 back.

Winston

Yeah, I see. But I don't think this algorithm would be faster than the one what I was talking about. Or would it?

Hi Alexey, yes I get what you are saying and I was going to ask the same thing. I wonder if there is an algorithm that can be passed a range of numbers and find what numbers in the range need to be used, and then process them numbers to return the smallest number. Its a little out of my league unfortunately but just a though

I've tested two approaches and here are some results of the tests:

**Calculating LCM for range [1,10]**

Variant #1

LCM is: 2520

Elapsed time is: 93115 nanoseconds

Variant #2

LCM is: 2520

Elapsed time is: 638 nanoseconds

**Calculating LCM for range [1,13]**

Variant #1

LCM is: 360360

Elapsed time is: 3873815 nanoseconds

Variant #2

LCM is: 360360

Elapsed time is: 319 nanoseconds

**Calculating LCM for range [1,17]**

Variant #1

LCM is: 12252240

Elapsed time is: 73464401 nanoseconds

Variant #2

LCM is: 12252240

Elapsed time is: 0 nanoseconds

**Calculating LCM for range [1,20]**

Variant #1

LCM is: 232792560

Elapsed time is: 1278957067 nanoseconds

Variant #2

LCM is: 232792560

Elapsed time is: 0 nanoseconds

I thought solving of this problem by Winston's approach would request some fancy and very slow algorithm, but I was so wrong. Results talk for themselves.

Thank you guys for steering me to the right solution and your patience! You rock, guys!

Alan Smith wrote:I wonder if there is an algorithm that can be passed a range of numbers and find what numbers in the range need to be used, and then process them numbers to return the smallest number. Its a little out of my league unfortunately but just a though

yes, there is. You have been given sufficient hints to find it, if you would read the suggested articles. And it is something that a 5th grader can do, so I doubt it is out of your league.

Aleksey Vladimirovich wrote:I don't think this algorithm would be faster than the one what I was talking about. Or would it?

if you are talking for a small range of numbers, probably not. But programmers thing about things as the data size gets REALLY large. I haven't done the math to figure out the complexity of each algorithm, but my hunch is that the more paring down you can do up front, the the better.

Aleksey Vladimirovich wrote:The sufficient condition will be to check only range: [(lowerBorderOfRange < upperBorderOfRange / 2 ? (int) upperBorderOfRange / 2 : lowerBorderOfRange), upperBorderOfRange]

That may be sufficient ( I haven't bothered to check), but it is certainly not NECESSARY. if you think about it, checking 1->upper bound of range is sufficient. Big deal. What's cool is to figure out the necessary AND sufficient.