It's a standard result that the number ω(N) of prime factors of N > 2 can be bounded above by$$ \omega(N) \;=\; \frac{\log(N)}{\log\log(N)} \big(1 + O\big(1/\log\log(N)\big)\big) \;.$$ Are tighter bounds known when N is logarithmically rough --- that is, where for some fixed constant c > 0, N has no prime factors smaller than c log(N)?

  • 3
    $\begingroup$ Unless my scribblings on the board are wrong, a short calculation shows that for any such fixed constant, the bound is exactly the same. The scribblings are the following: the largest $\omega$ is achieved by multiplying the primes between $y$ and $x$. To satisfy your condition, $y \sim \frac{c}{c+1}x$, so $N \sim e^{\frac{x}{c+1}}$ and $\omega(N) \sim \frac{x}{(c+1)\log(x)}$. $\endgroup$ May 7, 2010 at 16:01
  • $\begingroup$ Forgive me, I'm not a number theorist. It's clear that $\omega(N)$ is maximized by taking consecutive primes. But: (a) how do you obtain the bound $y\sim(\frac{c}{c+1})x$, and (b) how do you obtain the asymptotic growth of $N$ with respect to $x$? For the latter (given the ratio of $y$ to $x$ described) I obtain a rough bound of $N>\frac{x!}{[cx/(c+1)]!}\in\Omega\big((x/e)^{x/(c+1)}\big)$ , which is larger than the growth you describe. Could you elaborate further on your scribblings, or refer me to the (likely elementary textbook) reference where I could find the tools you're using? $\endgroup$ May 10, 2010 at 7:35
  • $\begingroup$ $N=\prod_{y<p<x} p \sim e^{x-y}$. The condition translates to $y > c\log(e^{x-y})=c(x-y)$ or $y>\frac{c}{c+1}x$. So taking equality we have $N \sim e^{\frac{1}{c+1}x}$ and $\omega(N) = \pi(x)-\pi(y) \sim x/\log(x)-cx/(c+1)\log(cx/(c+1)) \sim \frac{x}{(c+1)\log(x)}$. $\endgroup$ May 12, 2010 at 5:06
  • $\begingroup$ Okay, this seems fairly clear. Thanks. $\endgroup$ May 15, 2010 at 12:29
  • $\begingroup$ By $\omega(N)$ do you mean number of prime factors or number of distinct prime factors? $\endgroup$
    – gen
    Mar 18, 2019 at 15:53

1 Answer 1


The intuition is that $\log_{c\log N}N=\frac{\log N}{\log(c\log N)}=\frac{\log N}{\log c+\log\log N}$ which is asymptotically $\frac{\log N}{\log\log N}$. For this to work, we need that the kth prime for $k=\frac{\log N}{\log(c\log N)}+\pi(c\log N)\approx\frac{\log N}{\log\log N}$ to be 'close' to $c\log N$ -- actually, any constant multiple of $\log N$ will do.

$p_k\approx\frac{\log N}{\log\log N}\log\frac{\log N}{\log\log N}\approx\log N$, so $\log_{p_k}N\approx\frac{\log N}{\log\log N}$, as desired. This could probably made explicit with Rosser's theorem and/or Dusart's various bounds on $p_n$ and $\pi(n)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.