Sorry for my mistake..

Let's suppose that n = 2^x * 3^y * z. (where z is not divisible by 2 and 3) If we include n in set S, we cannot have 2n = 2^(x+1) * 3^y * z and 3n = 2^x * 3^(y+1) * z in set S.

Let's define a plane P[z] where z is not divisible by 2 and 3. For each positive integer i = 2^x * 3^y * z (<= N), draw a point (x, y) at P[z].

If we select the point (x, y) in P[z], then we cannot select the point (x+1, y) and (x, y+1) in P[z]. So the problem is: how many ways can we choose points such that the condition above is satisfied?

The value of x and y are very small, so we can do this in DP.