# Number of positive integers less than $x$ that can be written as product of powers of finite primes

Let $$p_1,p_2,...p_k$$ be a finite set of prime numbers. Prove that the number of positive integers $$n \leq x$$ that can be written in the form $$n=p_1^{r_1}p_2^{r_2}...p_k^{r_k}$$ is at most $$\prod_{i=1}^{k} (\frac{\log x}{\log p_i}+1)$$ Prove that if $$x$$ is sufficiently large, then there are positive integers $$n \leq x$$ that cannot be represented in this way.

I encountered this problem while going through the book "Elementary Methods in Number Theory" by Nathanson. Here, no additonal theory except the basic elementary facts about primes are given before this problem. Using these tools, can anyone please try and solve or give hints? I tried but I couldn't approach the problem.

• Just think about $p_1, r_1$. How big can $r_1$ be? Well, $p_1^{r_1}≤x\implies r_1\log p_1≤\log x$. Thus $r_1\in \{0,\big \lfloor \frac {\log x}{\log p_1}\big \rfloor\}$. Can you finish from there? – lulu May 21 '20 at 14:16
• Right! Yes, I got it. Thanks. – Dishant May 21 '20 at 14:23
• To be clear: the intent of the second part is to use this upper bound to prove that there are infinitely primes (if you know there are infinitely many primes then it is obvious that there are arbitrarily large numbers that can't be factored using just $p_1, \cdots, p_k$). You need to argue that, for sufficiently large $x$, that product is $<x$. – lulu May 21 '20 at 14:31

I think the comment is good enough for you to figure out the solution to the first part. The $$2$$nd part is even easier, you could use the fact that primes are infinite and use the fundamental theorem of arithmetic.