Let $a$ be a natural number such that the number of different prime divisors of $a$ is $2$. For example $6=2\times 3$, or $12=2^2\times 3$ or $225=3^2\times 5^2$.
Now find the number all $a$ less than 1000?
My attempt: we must use of the prime numbers $2,3,5,7,11,13,17,19,23,29,31$
On
On
The methods given so far require enumerating primes up to $500$, although Ross Millikan's comment on alex.jordan's answer suggests that only primes up to $\sqrt{1000}\approx31.623$ are needed. It isn't clear to me how alex.jordan's method is supposed to be adapted to avoid using primes greater than $31$, so I thought I'd show a different calculation that does so. Undoubtedly this can be made more efficient.
The integers $1$, $2$, $\ldots,$ $1000$ include
This leaves $1000-1-193-298=508$ integers with exactly two prime factors.
As shown below, the terms in this expression can be computed using only knowledge of primes less than or equal to $\sqrt{1000}$ and the principle of inclusion-exclusion.
To compute the number of primes between $1$ and $1000$, observe that a composite number in this interval is divisible by a prime less than or equal to $\sqrt{1000}$. Let $$ A=\{2,3,5,7,11,13,17,19,23,29,31\} $$ be the set of such primes. Then the set of primes between $1$ and $1000$ is the union of the disjoint sets $A$ and $B$, where $B$ is defined to be the set of integers between $2$ and $1000$ that are not divisible by any element of $A$. Now $\lvert A\rvert=11$ and $$ \begin{aligned} \lvert B\rvert=&999-\sum_{p\le31}\left\lfloor\frac{1000}{p}\right\rfloor+\sum_{p_1<p_2\le31}\left\lfloor\frac{1000}{p_1p_2}\right\rfloor-\sum_{p_1<p_2<p_3\le31}\left\lfloor\frac{1000}{p_1p_2p_3}\right\rfloor\\ &+\sum_{p_1<p_2<p_3<p_4\le31}\left\lfloor\frac{1000}{p_1p_2p_3p_4}\right\rfloor-\ldots \end{aligned} $$ All terms in the ellipsis are zero, as are most terms in the third and fourth summations. The result is that $\lvert B\rvert=157$ and therefore that there are $168$ primes between $1$ and $1000$. In addition, there are $11+7+4+2+1=25$ prime powers, including the $11$ squares of the elements of $A$ and higher powers of $2$, $3$, $5$, and $7$. Note that the fourth summation contains relatively few nonzero terms. The third summation is the most painful to compute, but this can, in fact, be avoided due to a cancelation, as shown below.
To compute the number of positive integers less than or equal to $1000$ with three or more prime factors, start with the sum $$ \sum_{p_1<p_2<p_3}\left\lfloor\frac{1000}{p_1p_2p_3}\right\rfloor. $$ This sum overcounts the integers with four prime factors. (Because the smallest integer with five prime factors is $2\cdot3\cdot5\cdot7\cdot11=2310$, we don't have to worry about integers with more than four prime factors.) Each integer with four prime factors is counted $\binom{4}{3}=4$ times in the sum, so the correct count of integers divisible by at least three primes is $$ \sum_{p_1<p_2<p_3}\left\lfloor\frac{1000}{p_1p_2p_3}\right\rfloor- 3\sum_{p_1<p_2<p_3<p_4}\left\lfloor\frac{1000}{p_1p_2p_3p_4}\right\rfloor. $$ Note that the summations in this expression are over all primes rather than primes less than or equal to $31$. The second summation, however, contains no nonzero terms involving primes greater than $31$ since the least product involving a prime greater than $31$ is $2\cdot3\cdot5\cdot37=1110>1000$. In the first summation, at most one of the primes, namely $p_3$, may be greater than $31$. Hence we may rewrite this expression as $$ \sum_{p_1<p_2<p_3\le31}\left\lfloor\frac{1000}{p_1p_2p_3}\right\rfloor+ \sum_{p_1<p_2\le31,\,p_3>31}\left\lfloor\frac{1000}{p_1p_2p_3}\right\rfloor- 3\cdot\sum_{p_1<p_2<p_3<p_4\le31}\left\lfloor\frac{1000}{p_1p_2p_3p_4}\right\rfloor, $$ which allows us to combine terms with similar terms in the expression above for $\lvert B\rvert$. (The first summation, in fact, cancels one of the summations in $\lvert B\rvert$.) The most straightforward way to compute the second summation is to write down all primes up to $1000/(2\cdot3)=1000/6$, that is, all primes up to $163$. But if you want to avoid using primes greater than $31$, you can do by observing that the only pairs $(p_1,p_2)$ that produce nonzero terms in the sum are $(2,3)$, $(2,5)$, $(2,7)$, $(2,11)$, $(2,13)$, $(3,5)$, and $(3,7)$. Taking $(2,3)$ as an example, since $2\cdot3=6$ and $1000/(6\cdot32)<6$, each prime greater than $31$ contributes at most $5$ to the sum. Adapting the prime counting method shown above, we find that
As a consequence, the total contribution of the pair $(p_1,p_2)=(2,3)$ to the sum is $5\cdot0+4\cdot2+3\cdot3+2\cdot7+1\cdot15=46$. A similar analysis of the other pairs shows that the total contribution of the second summation is $88$. These computations can be done using only primes up to $11$.
Putting all terms together gives $$ \begin{aligned} &1000-1-\lvert A\rvert-(\text{# prime powers})-\lvert B\rvert-(\text{# integers divisible by three primes})\\ &\quad=1000-1-11-25-999+\sum_{p\le31}\left\lfloor\frac{1000}{p}\right\rfloor-\sum_{p_1<p_2\le31}\left\lfloor\frac{1000}{p_1p_2}\right\rfloor-\sum_{p_1<p_2\le31,\,p_3>31}\left\lfloor\frac{1000}{p_1p_2p_3}\right\rfloor\\ &\qquad+2\cdot\sum_{p_1<p_2<p_3<p_4\le31}\left\lfloor\frac{1000}{p_1p_2p_3p_4}\right\rfloor\\ &\quad=1000-1-11-25-999+1560-974-88+2\cdot23\\ &\quad=508. \end{aligned} $$
Iterate $p$ downward starting from the highest prime below $500$. Iterate $k$ from $1$ to $\log_p(500)$. Iterate $q$ from $2$ up through primes less than $\frac{1000}{p^k}$. Iterate $j$ from $1$ to $\log_q(1000/p^k)$.
This captures all $p^kq^j$ that are less than $1000$.