According to the Prime Number Theorem, a number $n$, roughly speaking, has probability of primality $\sigma_n:=1/\ln n$.

As every schoolchild learns, one can test the primality of $n$ by looking for divisibility by primes up to $\sqrt{n}$. If these divisibility tests enjoyed independence, one would get ``probability of primality" equal to $$ \tau_n:=\prod_{p\leq \sqrt{n}} \frac{p-1}{p}\ .$$

Probability interpretations aside, one can examine the ratio $\sigma_n/\tau_n$. What limit, if any, does it approach? And how fast?

  • 2
    $\begingroup$ See the Mertens theorems as usual the optimal asymptotic depends on the Riemann hypothesis. If your question is if we find $\pi(x) \approx \frac{x}{\ln x}$ from $\prod_{n \le \sqrt{x}} (1-n^{-1})^{\pi(n) - \pi(n-1)} \approx \frac{\pi(x)}{x}$ the answer is yes. Making $\approx$ precise should give the Mertens theorem. $\endgroup$ – reuns May 16 at 22:20
  • 1
    $\begingroup$ theorem 429 in Hardy and Wright, the product for primes $p \leq t$ of your $(p-1)/p$ is about $e^{- \gamma}/ \log t$ This is due o Mertens $\endgroup$ – Will Jagy May 16 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.