Encontrar el 2,147,483,647 ésimo número primo

Question

En ciencias de la computación de una matriz es indexado por un número entero (int). A diferencia de las matemáticas, la ciencia de la computación entero (int) tiene un número finito de rango definido por la longitud de es fijo representación binaria.

En la mayoría de los modernos lenguajes de alto nivel el valor máximo de un entero es 2^31 - 1 (2147483647). Me gustaría crear una matriz de secuencial de los números primos en un programa de ordenador que tengo la intención de escribir.

Ejemplo:

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

Sin embargo, una matriz es indexado por un int , así que sólo puedo tener 2,147,483,647 entradas de la matriz. Debido a esto me gustaría saber cuál es el más grande de la prime me podrían colocar en la matriz de principal secuencial entradas.

Qué valor sería colocado en list[2147483647] = x; ¿Cuál es la 2,147,483,647 ésimo número primo?

No estoy pidiendo a nadie en particular, para calcular los números primos hasta que la iteración. Me pregunto cómo se podría ir sobre el cálculo o encontrar un lugar donde ya se ha precalculadas. Sé Wolfram tiene algunos precalculadas de los números primos, pero no pude encontrar el correcto primer tablas.

EDITAR: Hago esta pregunta porque yo vengo de una computación de fondo, no de las matemáticas y tengo dificultad para estimar el tamaño de la 2,147,483,647 ésimo número primo. Más bien, a continuación, el valor exacto, un áspero valor será suficiente. Sólo necesito saber cómo aproximadamente grande este es el primer.

1. Si representados en binario, más o menos cómo puede bits sería la de 2.147.483.647 th primer contienen?

2. Si representados en decimal, más o menos cómo puede dígitos sería la de 2.147.483.647 th primer contienen?

Answer 1

No estoy muy seguro de por qué usted necesita saber lo que el $2147483647$-ésimo número primo es, pero me imagino que es para que usted sepa qué tipo de datos para almacenar los elementos de la matriz.

En ese caso, sólo se necesita un valor aproximado. El Primer Número Teorema nos dice que

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

donde $\pi(n)$ es el número de números primos menos de $n$. Por lo que estamos buscando $n$ $\pi(n)\ge2147483647$ (a continuación, hay, al menos, $2147483647$ primos menos de $n$, por lo que, en particular, $2147483647$ de los números primos son todos más pequeños que $n$, y se pueden almacenar en variables de tamaño de $n$).

Vamos a ignorar el $\approx$ signo y tratarla como una igualdad. Esto significa que accidentalmente podría obtener un valor que es demasiado pequeña, pero vamos no te preocupes por eso.

Así que queremos

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

Wolfram|Alpha ofrece una respuesta de $5.303\times 10^{10}$$n$.

Ahora $\log_2(5.03\times 10^{10})\approx 35.5$, por lo que había necesidad de 36 bits para almacenar el número.

$\log_{10}(5.03\times10^{10})\approx 10.7$, por lo que necesitaría $11$ dígitos para representar el $2147483647$-ésimo número primo en decimal.

Answer 2

Para que no haya una respuesta: Como Artes ha demostrado, el exacto prime es $50685770143$. Esto ha $11$ dígitos decimales. En binario, es $101111001101000110110111100110011111_2$, lo que ha $36$ bits.