Assume we are given a number $n>3$.
Define a prime power as a number of the form $p^r$, where $p \in \mathbb P$ and $r \in \mathbb N, \ r >0.$
We would like to know how many distinct prime powers are needed to express all composite numbers up to $n$. In other words, if we hold not only primes but pure prime powers like $5^2$ as distinct in the composition of a number and still count all numbers but primes as composites, how large a "vocabulary" of such numbers is needed to express all composites up to $n$?
Define a function $C: \mathbb N \rightarrow \mathbb N$ where $C(n)$ is the number distinct prime powers needed to express all composite numbers up to $n$.
Does there exist a "simple" formulation of $C(n)$, where simple means not involving sums where either the summation index or summands involve floor or ceiling functions or the like? Purely combinatorial justifications or intuition would also be nice.
A few values of $C(n):$
$$ \begin{array}{c|lcr} n & C(n) \\ \hline 4 & 1 \\ 6 & 3 \\ 10 & 6 \\ 100 & 25 \\ 1000 & 120 \\ \end{array} $$
Some inequalities:
\begin{equation} n-\pi(n)-1>C(n) \ \ \ \ \ (1), \end{equation} \begin{equation} C(n)>\pi \left( \frac{n}{2} \right) \ \ \ \ \ (2), \end{equation}
where $\pi(n)$ is the prime-counting function.
(1) is clear, because the lhs is the number of composite numbers up to $n$ minus 1, because 1 is not a composite in this context, and clearly we need less than this number of prime powers, because not every composite needs a new prime power in its composition.
(2) follows from the fact that $\pi \left( \frac{n}{2} \right)$ is the number of distinct primes smaller than $n/2$ and clearly we need all of them. Consider a sequence $(2k), \ k=1,2,3\dots n/2.$ Here $k$ includes all primes smaller than $n/2$.
Edit:
The "non-simple" formula for $C(n)$ would be:
\begin{equation} C(n) = \pi \left( \frac{n}{2} \right)+\sum_{k=2}_{k \in \mathbb P}^{\lfloor \sqrt{n} \rfloor} \left( \lfloor \frac{\log n}{\log k} \rfloor -1 \right) \end{equation}
Because we need all primes $\pi \left( \frac{n}{2} \right)$ and the $\lfloor \frac{\log n}{\log k} \rfloor $ tells the greatest power a prime can be raised for it to be smaller than $n$. But this counts the single power too, so we need to subtract the 1. The index goes to $\lfloor \sqrt{n} \rfloor$ because this is the magnitude of the greatest prime whose square can be smaller than $n$.
This can be simplified further, by simple removing the need for prime counting function altogether:
\begin{equation} C(n) = \sum_{k=2}_{k \in \mathbb P}^{\frac{n}{2} } \left( \lfloor \frac{\log n}{\log k} \rfloor \right) \end{equation}
If i understood what you ask, you want the number of prime powers up to $n$.
Then you could define $C(n)$ as $\pi^*(n)$
(Erdos calls it like that in his famous book :Topics in the Theory of Numbers)
We can see that $\pi^*(n)=\pi(n)+\pi(\sqrt n)+\pi(\sqrt[3]n)+...$.
The summation ends at the $k$th root, when $k\leq \frac{lnn}{ln2}$
So it is easy to see that $\pi^*(n)$ behaves like $\pi(n)$ because the above sum is not greater than $\pi(n)+(k-1)\pi(\sqrt n)$ which is asymptoticaly equal to $\pi(n)$
So,if you want an elementary bound :there are constants $a,b$ with
$\frac{an}{lnn}<\pi^*(n)<\frac{bn}{lnn}$
(But don't expect anything better at all if you want my opinion)