CODEWITHSUNDEEP
mathdivision
naskobg13
naskobg13

Reputation: 79

Find all numbers only divisible by 3, 5 and 7

I was asked on an interview to find all numbers only divisible by 3, 5 and 7. I purposed we can make check like 

if (num%3==0 || num%5==0 || num%7==0) 
  return true 
else 
  return false.

But in this case if we have 6 it will pass the test but its also divisible by 2 so this doesn't work. Can you purpose something? I am using java. Find mean to check if some number is divisible only to this number

Upvotes: 0

Views: 7702

Answers (3)

user448810
user448810

Reputation: 17866

We first note that 1 is a member of the set. Although it is not divisible by 3, 5 or 7, neither is it divisible by any number other than 3, 5 or 7, so we will say that 1 is in the set. This conforms to the mathematical definition of the set { x = 3i · 5j · 7k | i, j, k ≥ 0 }.

One method is to count from 1, adding 2 at each step, and checking if the number is divisible only by 3, 5 and 7. That's slow because it does a lot of work that immediately gets discarded, since there are many fewer numbers divisible only by 3, 5 and 7 than there are odd numbers.

A better approach is to generate the desired numbers directly, by induction. The number 1 is in the set, and for any x in the set, so are 3 x, 5 x and 7 x. So the algorithm to generate all numbers divisible only by 3, 5 and 7, in order, is:

1. Initialize a priority queue with the number 1.
2. Pop the smallest number in the priority queue, call it x.
3. Add 3x, 5x and 7x to the priority queue.
4. Output x as the next integer in the set.
5. If you want more output, go to Step 2.
6. Halt.

I implemented both algorithms; you can see them at http://ideone.com/YwnAQ8. The brute-force method takes a little over ten seconds to find the 203 members of the 3,5,7 set less than a million; the priority queue does the same calculation in a hundredth of a second, a thousand times faster. The priority queue implementation used there is explained at my blog. You can also see the set of 3,5,7 numbers at OEIS.

Upvotes: 2

anon
anon

Reputation:

I won't give you a Java algorithm, as it should be fairly easy to implement.

You can just:

1. check if (n%3 == 0)
2. if it is, set n /= 3 and repeat step 1.
3. do the same for the number 5 and 7
4. now if n != 1, return false, else return true

In a Java algorithm:

// n is some random natural number
if (n == 1 || n == 0)
    return false

while (!n%3) 
{
    n /= 3;
}
while (!n%5)
{
    n /= 5;
}
while (!n%7)
{
    n /= 7;
}
if (n == 1)
{
    return true;
}
else
{
    return false;
}

It's not the best syntax, I'm just giving an straight-forward implementation of the algorithm presented above.

Upvotes: 2

Degustaf
Degustaf

Reputation: 2670

I would approach this by removing all of the factors of 3, 5, and 7 from the original number, and seeing what's left.

while(num % 3 == 0)
{
    num = num / 3;
}
while(num % 5 == 0)
{
    num = num / 5;
}
while(num % 7 == 0)
{
    num = num / 7;
}

return (num == 1);

Upvotes: 4

Related Questions