Prime Numbers – Finding the 2,147,483,647th Prime Number

computer scienceprime numbers

In computer science an array is indexed by an integer (int). Unlike in mathematics, the computer science integer (int) has a finite range defined by the length of it's fixed binary representation.

In most modern higher level languages the maximum value of an integer is 2^31 - 1 (2147483647). I would like to create an array of sequential primes in a computer program I intend to write.

Example:

  list[0] =  2;
  list[1] =  3;
  list[2] =  5;  
  list[3] =  7;  
  list[4] = 11;  etc...

However, an array is indexed by an int so I can only have 2,147,483,647 entries in the array. Because of this I would like to know what the largest prime I could place in the array of sequential prime entries.

What value would be placed in list[2147483647] = x; What is the 2,147,483,647th prime number?

I'm not asking anyone in particular to calculate primes up to that iteration. I'm wondering how I might go about calculating it or find a place where it has already been precomputed. I know Wolfram has some precomputed primes but I couldn't find the correct prime tables.

EDIT:
I ask this question because I come from a computing background, not mathematics and I have difficulty estimating the size of the 2,147,483,647th prime number. Rather then the exact value, a rough value will suffice. I just need to know how roughly large this prime is.

  1. If represented in binary, roughly how may bits would the 2,147,483,647th prime contain?

  2. If represented in decimal, roughly how may digits would the 2,147,483,647th prime contain?

Best Answer

I'm not quite sure why you need to know what the $2147483647$-th prime number is, but I'm going to guess it's so you know what data type to store the elements of the array in.

In that case, you only need an approximate value. The Prime Number Theorem tells us that

$$\pi(n)\approx\frac{n}{\log(n)}$$

where $\pi(n)$ is the number of prime numbers less than $n$. So we are looking for $n$ with $\pi(n)\ge2147483647$ (then there are at least $2147483647$ primes less than $n$, so in particular the first $2147483647$ primes are all smaller than $n$, and can be stored in variables of size $n$).

Let's just ignore the $\approx$ sign and treat it as an equality. This means we might accidentally get a value that's too small, but let's not worry about that.

So we want

$$\pi(n)=\frac{n}{\log(n)}=2147483647$$

Wolfram|Alpha gives an answer of $5.303\times 10^{10}$ for $n$.

Now $\log_2(5.03\times 10^{10})\approx 35.5$, so you'd need 36 bits to store that number.

$\log_{10}(5.03\times10^{10})\approx 10.7$, so you'd need $11$ digits to represent the $2147483647$-th prime number in decimal.

Related Question