I have come across two papers that invoke the prime number theorem, without actually explaining how exactly they arrive at their conclusions. The claims in question are highlighted in bold.
First Paper
In theorem 2 of
Demaine, Erik D.; Eisenstat, Sarah; Shallit, Jeffrey; Wilson, David A., Remarks on separating words, Holzer, Markus (ed.) et al., Descriptional complexity of formal systems. 13th international workshop, DCFS 2011, Gießen/Limburg, Germany, July 25–27, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22599-4/pbk). Lecture Notes in Computer Science 6808, 147-157 (2011). ZBL1341.68087.
(Screenshot of relevant portion)
the authors make the following argument:
Let $n\in \mathbb N$ and $a_1, \ldots, a_d \in\mathbb N$, with each $a_i$ being at most $n$. Let $N=a_1\cdot a_2\cdots a_d$.
Then $N\leq n^d$. By the prime number theorem, there exists some prime $p=O(\log N)=O(d \log n)$ such that N is not divisible by $p$.
How does the PNT prove this? I was under the impression that the PNT states that the $m$-th prime number is of order $O(m \log m)$. Each $a_i$ can have at most $\log n$ many distinct prime factors, so $N$ can have at most $O(d\log n)$ many distinct prime factors, so there must be a prime among the first $O(d \log n)$ primes that does not divide $N$. This would make $p$ be of order $O((d\log n)\log(d\log n))$. What am I missing here?
Second Paper
In Lemma 3 of
Robson, J. M., Separating strings with small automata, Inf. Process. Lett. 30, No. 4, 209-214 (1989). ZBL0666.68051.
(Screenshot of relevant portion)
the author makes the following argument:
Let $$n, l, j\in\mathbb N\text{ and}\\\alpha\in\mathbb R,$$ such that $$0<\alpha<1\text{ and}\\l\leq n^\alpha.$$ Also suppose that $j$ is a prime number that is at most the $\frac{2n}{l(1-\alpha)}$-th prime number greater than $\frac n l$, then there exists a constant $c$, depending only on $\alpha$, such that one of the following is true (I don't know which one, since the typesetting in the paper is a bit ambiguous here). Either $$j \leq \frac c l n \log n$$ or $$j \leq cn\log\frac n l.$$ The former makes more sense to me, considering how the lemma is used in the proof of theorem 1, but perhaps I'm also doing that derivation wrong.
Either way, it seems to me that $j$ would be at most the $m$-th prime number, where $$m = \pi\left(\frac n l\right) + \frac{2n}{l(1-\alpha)}$$ with $\pi$ of course being the prime counting function. So (by the PNT) $m$ would be on the order $$O\left(\frac n l \frac 1 {\log \frac n l} + \frac{2n}{l(1-\alpha)}\right).$$ Add to this the fact that the bound on $j$ would now be given as $O(m\log m)$ and it ends up looking nothing like the bound given in the paper.
In the proof of theorem 2 we have a situation similar to the one in the first paper.
(Screenshot of relevant portion)
Here we have $X^2$ different natural numbers $a_i$ ($1\leq i\leq X^2$), each of them being at most $n \in \mathbb N$. Again we have $0<\alpha<1$. We want to find the smallest prime number $q$ that does not divide any of the $a_i$. Since none of the $a_i$ can have more than $\frac 1 \alpha$ distinct factors greater than $n^\alpha$, each $a_i$ can only eliminate at most $\frac 1 \alpha$ such primes. In total that would be at most $\frac {X^2} \alpha$ many. So an upper bound on $q$ would be the $m$-th prime number, where $$m = \pi\left(n^\alpha\right)+\frac{X^2}\alpha.$$ As in the second example, this would lead to a widely different bound than the $O(X^2\log n + n^\alpha)$ given in the paper.
Any help in understanding the results would be greatly appreciated.