Here's the task:

Write a program which takes input from the user - a number. Then without using if statement you should print on the screen whether or not the number is divisible by each one of the integers: 2, 3, 4, ... 9, 10.

The idea is to use the ternary operator for a simple check instead of making 8-9 if statements which check for each integer. But don't think about the programming side of things, I just want to make sure my logic is correct:

My idea is the following: the input would be divisible by each one of these if it's divisible by a specific product of these numbers.

So I took all prime integers from this sequence, because they can't be represented as a composite of the product of smaller integers. So far we have: 2,3,5,7.

Since 2*3 = 6, then we don't need to check if the number is divisible by 6. Since 2*5 = 10, we don't need to check if the number is divisible by 10. So we're left to decide if 4, 8 and 9 should be in the product. Since we can't get 4 out of the product of some of 2,3,5,7, then we'll add 4 to the group. Now we have: 2,3,4,5,7.

We don't have to check for 8, since 2*4 = 8. If we add 9, then the group becomes: 2,3,4,5,7,9. But if the input is divisible by 9, then it is divisible by 3. So we can exclude 3 out of the product group.

We're left with 2,4,5,7,9. The product of these is 2520. So if the input is divisible by 2520, then it's divisible by all the numbers from 2 to 10. Is that correct?

  • $\begingroup$ $5,7,8,9$ is the list of the maximum powers of primes $\le 10$ and their product is indeed $2520$. $\endgroup$ – dxiv Oct 24 '16 at 19:03
  • $\begingroup$ You are right. If the number is divisible by $lcm(2,3,4,5,6,7,8,9,10)=2520$ then it is divisible by $2,3,4,5,6,7,8,9,10.$ $\endgroup$ – mfl Oct 24 '16 at 19:05

Your answer is correct but the logic is faulty. You want to find the highest power of each prime that is represented in your set of divisors, so need $8=2^3$ for that reason. If the set of numbers you were to check were $\{2,3,4,5,6,7\}$ your logic would have both $2$ and $4$ and demand divisibility by $8$, which is not required.

  • $\begingroup$ Thank you for the correction. $\endgroup$ – Mr. Nicky Oct 24 '16 at 19:14

if your intention is to write a code and check whether a number is divisible by a set of numbers. you can always use the floor function $$S=\sum_{i=1}^{k}n/a_{i}-\lfloor{n/a_{i}}\rfloor$$ and if $S=0$ your number is divisible by your set if not it ain't.

  • $\begingroup$ Is not simpler to check divisibility by the lcm? $\endgroup$ – mfl Oct 24 '16 at 19:42
  • $\begingroup$ @mfl for this case yes, but if a set of 100 numbers are given i think this algorithm would be faster. though i can't tell for sure $\endgroup$ – avz2611 Oct 24 '16 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.