Numbers up to 1000 divisible by 2 or 3 and no other prime My task requires to find all numbers from $1-1000$ such that they are divisible by $2$ or $3$ and no other primes. I know that $2$ divides even numbers and I can use the formula $\left \lfloor{\frac{1000}{2}}\right \rfloor $ and the numbers divisible by three $\left \lfloor{\frac{1000}{3}}\right \rfloor $. Also we rule out the numbers that are divisible by both, so by $6$ $\left \lfloor{\frac{1000}{6}}\right \rfloor $. In total we get that there are $500+333-166=667$ numbers divisible by $2$ or $3$. However I also need to make sure that I $\textit{only}$ count numbers divisible by either of these $2$. Is there a quick way to do it?
 A: Such a number should be in the form of $2^m3^n$ where $m$ and $n$ are non-negative integers such that $m$ and $n$ are not both zero.
If $n=0$, $m\ge1$ and $2^m\le1000$. So $1\le m\le 9$.
If $n=1$, $2^m\le\frac{1000}{3}$. So $0\le m\le 8$.
If $n=2$, $2^m\le\frac{1000}{9}$. So $0\le m\le 6$.
If $n=3$, $2^m\le\frac{1000}{27}$. So $0\le m\le 5$.
If $n=4$, $2^m\le\frac{1000}{81}$. So $0\le m\le 3$.
If $n=5$, $2^m\le\frac{1000}{243}$. So $0\le m\le 2$.
If $n=6$, $2^m\le\frac{1000}{729}$. So $m= 0$.
If $n=7$, $2^m\le\frac{1000}{2187}$, which is impossible.
Number of possibilities is $9+9+7+6+4+3+1=39$.
A: You want numbers of the form $2^a3^b$ where $a,b \geq 0$ and not both are equal to $0$. Trivial check gives that $a\leq9, b\leq6$. You can do case-by-case work:
$1)$ $a=0$. You get $6$ possibilities for $6$ since $b\neq0$ in this case
$2)$ $a=1$. You get $3^b\leq500$, hence $6$ solutions
$3)$ $a=2\Longrightarrow6$ solutions
$4)$ $a=3\Longrightarrow5$ solutions
$5)$ $a=4\Longrightarrow4$ solutions
$6)$ $a=5\Longrightarrow4$ solutions
$7)$ $a=6\Longrightarrow3$ solutions
$8)$ $a=7\Longrightarrow2$ solutions
$9)$ $a=8\Longrightarrow2$ solutions
$10)$ $a=9\Longrightarrow1$ solution
Sum all those solutions and you are good to go! The answer is 39
A: did you notice that the numbers which are divisible by 2 or 3 but not other prime are just all powers of 2 (below 1000), all powers of 3 (below 1000) and any product of them (below 1000)? and they are very few of them... $2^9$ is the last power of 2 below 1000, $3^6$ is the last power of 3 below 1000, and the biggest combination of them is $2^3\times 3^4$.
