
We will find a lower bound on the number of composite numbers less
than one million.  This will give an upper bound on the number of
primes less than one million.  Define the following sets:

\begin{eqnarray*}
S_2 & = & \{ 4, 6, 8, 10, \ldots, 1000000 \} \\
S_3 & = & \{ 6, 9, 12, 15, \ldots, 999999 \} \\
S_5 & = & \{ 10, 15, 20, 25, \ldots, 1000000 \} \\
S_7 & = & \{ 14, 21, 28, 35, \ldots, 999999 \}
\end{eqnarray*}

The union of these sets is a subset of the composite numbers less than
one million.  Therefore, the size of the union of these sets is a
lower bound on the number of composite numbers less than 1000000.  By
the inclusion-exclusion principle,

\begin{eqnarray*}
|S_2 \cup S_3 \cup S_5 \cup s_7| & = &
	|S_2| + |S_3| + |S_5| + |S_7|
	- |S_2 \cup S_3| - |S_2 \cup S_5| - |S_2 \cup S_7|
	- |S_3 \cup S_5| - |S_3 \cup S_7| - |S_5 \cup S_7|
	+ |S_2 \cup S_3 \cup S_5| + |S_2 \cup S_3 \cup S_7|
	+ |S_2 \cup S_5 \cup S_7| + |S_3 \cup S_5 \cup S_7|
	- |S_2 \cup S_3 \cup S_5 \cup S_7|
\end{eqnarray*}

We can compute the sizes of all the above sets using simple, if
tedious arithmetic.  For example:

\begin{eqnarray*}
|S_3 \cup S_5 \cup S_7|
	& = &	| \{ 105, 210, 315, \ldots, 999915 \} | \\
	& = &	\left\lfloor \frac{1000000}{105} \right\rfloor \\
	& = &	9523
\end{eqnarray*}

Plugging the set sizes into the inclusion-exclusion formula gives:

\begin{eqnarray*}
|S_2 \cup S_3 \cup S_5 \cup s_7| & = &
	499999 + 333332 + 199999 + 142856
	- 166666 - 100000 - 71428 - 66666 - 47619 - 28571
	+ 33333 + 23809 + 14285 + 9523
	- 4761 \\
	& = &	771425
\end{eqnarray*}

Among numbers less than one million, the number 1 is neither prime nor
composite, and at least 771425 numbers are composite.  Therefore,
there are at most $1000000 - 1 - 771425 = 228574$ primes.  Thus, at
most a quarter of the numbers less than one million are prime.

The actual number of primes less than one million is only 78498, so
our upper bound is quite loose.