Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I heard this question a few days ago, so reciting from memory:

If I were to randomly choose an arbitrarily large positive integer $n$, could I write a function that determines the likelihood of it being prime?

Intuitively, what would it mean to assign a probability to an integer of being prime?

Edit 1

I'm not sure how to incorporate the prime-counting function into this.

Edit 2

Alright, so the page on the prime number theorem says that:

Informally speaking, the prime number theorem states that if a random integer is selected in the range of zero to some large integer N, the probability that the selected integer is prime is about 1 / ln(N), where ln(N) is the natural logarithm of N.

Looking through the references, though, I can't find a more formal proof. So I will revise my question.

For a random integer selected in the range of $0$ to some large integer $N$, prove that the probability the selected integer is prime is $\frac{1}{\ln{N}}$.

Edit 3

If the selected integer $n$ was prime, it's necessary that it has no prime factors $p\leq\sqrt{n}$. If we could find the probability that $n$ is divisible by $p$ as some function of $p$, then could we write$$\prod_{p=2}^{\sqrt{n}}\left(1-f(p)\right)$$where $f(p)$ is the probability that $n$ is divisible by $p$?

share|cite|improve this question
At the very least you would first have to define exactly what you mean by picking an integer at random. – Brian M. Scott Nov 10 '12 at 10:48
Is this a field of study? See probabilistic number theory. – Did Nov 10 '12 at 11:01
I think this proof is a rewarding one to study. – Dan Brumleve Nov 10 '12 at 11:47
up vote 1 down vote accepted

Care should be taken in the sense we take the "density" of primes.

The prime number theorem states that $$ \pi(n)=\frac{n}{\log(n)}+O\left(\frac{n}{\log(n)^2}\right)\tag{1} $$ Thus, $$ \begin{align} \pi(n(1+\alpha))-\pi(n) &=\frac{n(1+\alpha)}{\log(n)+\log(1+\alpha)}-\frac{n}{\log(n)}+O\left(\frac{n}{\log(n)^2}\right)\\ &=\frac{n(1+\alpha)}{\log(n)}-\frac{n}{\log(n)}+O\left(\frac{n}{\log(n)^2}\right)\\ &=\frac{\alpha n}{\log(n)}+O\left(\frac{n}{\log(n)^2}\right)\tag{2} \end{align} $$ Therefore, $$ \frac{\pi(n(1+\alpha))-\pi(n)}{\alpha n} =\frac1{\log(n)}+O\left(\frac1{\alpha\log(n)^2}\right)\tag{3} $$ In the sense of $(3)$, the density of primes is $\dfrac1{\log(n)}$.

share|cite|improve this answer
A very cool solution. Thanks! – rnmartingale Nov 10 '12 at 21:34

On your second question, what it might mean to assign a probability to the likelihood of a number being prime, you might want to take a look at this answer, the discussion in the comments under it, and in particular the book that I refer to there, Towards a Philosophy of Real Mathematics by David Corfield.

share|cite|improve this answer
Thanks for the link, I'll take a day to read and understand what's going on before returning to this question. – rnmartingale Nov 10 '12 at 11:29

By the prime number theorem it is usually accurate to assume as a heuristic that the probability that $n$ is prime is about $\frac{1}{\log{n}}$.

share|cite|improve this answer
Thanks for the reference, I should incorporate this into my question. – rnmartingale Nov 10 '12 at 10:58
But you have reworded the title in such a way that the question is less answerable. You might also like to consider the Riemann hypothesis and Cramér's conjecture. – Dan Brumleve Nov 10 '12 at 11:12
I'm sorry, I'm trying to avoid vagueness. How would you suggest I change my question? – rnmartingale Nov 10 '12 at 11:19
There is no easy way to narrow it down. I think vaguer is better. – Dan Brumleve Nov 10 '12 at 11:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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