Get numbers that have only 2,3 and 5 as prime factors I am given an integer N. I have to find first N elements that are divisible by 2,3 or 5, but not by any other prime number.

N = 3
Results: 2,3,5
N = 5
Results: 2,3,5,6,8


Mistake number = 55.. 55/5 = 11.. 11 is prime number.. so means that it divides by any other prime number and doesn't counts in..

I guess there is need of recursive function,but I cant imagine what would algorithm look like

I was sent here from stackoverflow.

They gave me advice.. 2^i*3^j*5^k , for i,j,k = 0,1,2... , but it won't give an ordered array, because 2*2 &lt; 2*3 .. and so on 

I am trying to get this work in C++
The algorithm in this answer, in the end, is the same as the one in Bill Dubuque's answer, but I hope to be more elaborate and describe how one could arrive at the algorithm. Let's frame the problem as that of building the list of all such numbers in ascending order, i.e., each time adding to the list the smallest number that is not already in it.

First, note that all the numbers you want are of the form $2^i3^j5^k$, where $i, j, k$ are nonnegative integers. This means that after the first number $1$ (corresponding to $i = j = k = 0$), each "next" number can be obtained by multiplying some number already generated in the list, by either $2$, or $3$ or $5$.

So you start the list with the first number, $1$. To find the next number, you have three choices: multiply the number $1$ by either $2$, or $3$, or $5$. Since you want the smallest result, you pick $2$, and your list becomes $[1, 2]$. 

Now you can no longer multiply $1$ by $2$ to get a new number, it is "used up". Your three choices now are: multiplying $1$ by $3$, multiplying $1$ by $5$, or multiplying $\color{red}{2}$ by $2$. The smallest result is from multiplying $1$ by $3$, so you add the result to the list, which becomes $[1, 2, 3]$.

Now you can no longer multiply $1$ by $3$, it is "used up" for multiplication by $3$. The smallest number you can multiply by $3$ is the next number, $2$. Your three choices now are: multiplying $\color{red}{2}$ by $2$, multiplying $\color{red}2$ by $3$, and multiplying $1$ by $5$. You pick the smallest result, which corresponds to multiplying $2$ by $2$ and gives you $4$ which you add to the list, and now $2$ is also used up for multiplication by $2$ and for multiplication by $2$ you have to go to the next number in the list, namely $3$.

In general, you always have three choices: one number that you can multiply by $2$, another that you can multiply by $3$, and another that you can multiply by $5$. You pick whichever of these three choices gives the smallest result, and update the choice ("advance the pointer") for 2 or 3 or 5, whichever you chose.



The first few steps worked out explicitly:

List is $[1]$. Choice for 2 is $1$, choice for 3 is $1$, choice for 5 is $1$. (Choose multiplication by 2.)

List is $[1, 2]$. Choice for 2 is $2$, choice for 3 is $1$, choice for 5 is $1$. (Choose multiplication by 3.)

List is $[1, 2, 3]$. Choice for 2 is $2$, choice for 3 is $2$, choice for 5 is $1$. (Choose multiplication by 2.)

List $[1, 2, 3, 4]$. Choice for 2 is $3$, for 3 is $2$, choice for 5 is $1$. (Choose multiplication by 5.)

List is $[1, 2, 3, 4, 5]$. Choice for 2 is $3$, for 3 is $2$, for 5 is $2$. (Choose multiplication by 2.)

List is $[1, 2, 3, 4, 5, 6]$. Choice for 2 is $4$, for 3 is $3$ (note that we updated this also), for 5 is $2$. (Choose multiplication by 2.)

List is $[1, 2, 3, 4, 5, 6, 8]$. Choice for 2 is $5$, for 3 is $3$, for 5 is $2$. (Choose multiplication by $3$.)

List is $[1, 2, 3, 4, 5, 6, 8, 9]$. Choice for 2 is $5$, for 3 is $4$, for 5 is $2$. 

List is $[1, 2, 3, 4, 5, 6, 8, 9, 10]$. Choice for 2 is $6$, for 3 is $4$, for 5 is $3$.

List is $[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]$. Choice for 2 is $8$, for 3 is $5$, for $5$ is $3$.

List is $[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15]$. Choice for 2 is $8$, for 3 is $6$, for $5$ is $4$.



In code, you could implement it as a growing array, with three array indices pointing to the choices for 2, 3, and 5. Here is a complete working Python program (time.sleep is to keep it slow enough to see the output):

import time
num = [1]
c2 = c3 = c5 = 0

while True:
  next = min(2*num[c2], 3*num[c3], 5*num[c5])
  num.append(next)
  print num
  if next == 2*num[c2]: c2 += 1
  if next == 3*num[c3]: c3 += 1
  if next == 5*num[c5]: c5 += 1
  time.sleep(0.5)
Make a loop over numbers i.  Check the numbers one at a time, it doesn't need to be recursive.

Added:
If you want, you can use a nice recursive algorithm f(i) which is true or false depending on whether the number i should be allowed into the list.
f(i):
if i == 1: return true
else if i % 2 == 0: return f(i/2)
else if i % 3 == 0: return f(i/3)
else if i % 5 == 0: return f(i/5)
else: return false

Added:
Start the loop at 2, otherwise this function will wrongly allow 1 into the list.