Cuántos pares de números primos existen que $pq < 10^6$

Question

Estoy tratando de implementar esta función en mi programa, por lo que creo que debo encontrar que el número de pares $$(p, q)$$ such that both p, q are prime numbers and: $% $ $p\cdot q < 10^6$

No soy muy bueno en teoría del número, sé que hay $78498$ ceba bajo 1 millón, pero sé que sólo algunos de los números primos forman combinaciones que son menos 1 millón.

Gracias de antemano.

Answer 1

Hay $$\sum_{\substack{p\text{ prim}\\p\,\le\, 10^6}}\pi\left(\frac{10^6}p\right)=419902$$

pares, donde $\pi(x)$ es la primer función de conteo. $10^6$ no es el producto de dos números primos. Así que basta contar para cada prime $p\le 10^6$ el número de números primos $q$ menos de o igual a $10^6/p$, debido a que, a continuación,$pq<10^6$. En realidad, sólo tenemos que comprobar $p\leq 10^6/2$ como el más pequeño de otros destacados para multiplicar con es $2$.

Elegí este formulario de arriba, porque esto era realmente factible calcular en mi pc usando Mathematica. Mathematica ciertamente implementa una eficiente versión de $\pi(x)$.

---

Aquí aún es una versión más rápida para ejecutar (motivado por Roddy):

$$2\cdot\sum_{\substack{p\text{ prim}\\p\,\le\, 1000}}\pi\left(\frac{10^6}p\right)-\pi(1000)^2=419902.$$

Utiliza al menos uno de los factores tiene que ser en la mayoría de las $1000=\sqrt{10^6}$. Así que suma sólo a través de los números primos $p\le 1000$. El factor de $2$ cuenta para el volteado de la versión $(p,q)\to(q,p)$. Como esto lo cuenta todo dos veces con $p,q\le 1000$, tenemos que restar esta en la final.

Answer 2

El número de números menores que 1000000 con k factores primos son:

k=1: 78498, k=2: 210035, 3: 250853, 4:198062, 5:124465,6: 68963, 7: 35585, 8: 17572, 9: 8491, 10: 4016, 11: 1878, 12: 865, 13: 400, 14: 179, 15: 79, 16: 35, 17: 14, 18: 7, 19: 2.

El número de números primos $pq\leq 10^6 = 210035.$

Básicamente, usted tiene que escribir un programa que cuente el número de números primos en cada número y ordenar a través de ellos. La generalizada primer número teorema proporciona una rápida estimación de lo que es bueno para k pequeño en comparación con $\log_2 n.$

Answer 3

Acaba de hacer una lista de los números primos hasta $5\times10^5$ dejar de ser $l_1$. Crear una lista para almacenar $p$ $q$ dejar de ser $l_2$. Iterar sobre la lista del primer elemento y dejar que el elemento que se obtiene por cada iteración se $p$. Introduce $l_1$ mediante la eliminación de todos los elementos menos de $p$ a de una función a lo largo de con $l_2$, el trabajo de la función es la siguiente - Iterar sobre la lista a partir de la $p$ y dejar que el elemento de llegar a cada vez ser $q$. Comprobar a cada paso si $pq$ es de menos de un millón si es de tienda $p$ $q$ en la lista y si no es la de romper.