Hola 
Cómo están?
Quería mostrar algo.
Por el momento lo estoy trabajando para intentar formalizarlo matemáticamente. Pero he desarrollado en código un programa que es capaz de darme todos los primos hasta n, y al contarlos me dice cuantos números primos hay hasta dicho número.
Trabaja como una especie de criba con un conjunto notablemente reducido de números. Originalmente lo hice con excel, y ahi fui probando. Entonces ya cuando quise probar mas cantidad de números directamente hizo algo para no hacerlo manual.
Esto es lo que salió:
Con Python tienes también este código que es muy cortito y muy rápido, es la criba de Eratóstenes
n =set()
for p in range (2, 1000+1):
if p not in n:
print (p)
n.update(range (p*p, 1000+1, p))
Sólo eso.
Te lo explico:
Se define el conjunto de los números naturales con este comando n=set()
Este conjunto todavía no está formado, empieza siendo vacío y se irá rellenando según corre el programa.
Python tiene el comando “set”, el cual, a diferencia de las listas o matrices y demás, no repite números o elementos; es decir, si introducimos un número que ya está dentro, no lo mete y no aumenta la cantidad de elementos. Es tal como un conjunto matemático, los elementos son únicos, no existen repeticiones.
Después, se define hasta qué número va a alcanzar el conjunto empezando desde de 2 en adelante; y se define con este otro comando: for p in range (2, 1000+1)
En este caso he puesto hasta 1000, como podría haber puesto hasta un número mas grande, y nos dará al final todos los primos menores que 1000.
A la vez, con esa instrucción se está definiendo la variable “p”, en la que van entrando los números “n” en principio, pero después sólo se imprimirán los primos, como se va a ver en las siguientes instrucciones.
Mientras el bucle va corriendo, la instrucción siguiente analiza qué números van entrando con el “si” condicional que aparece en ella: if p not in n
y que dice 'si “j” no está en “n”'
Como al inicio todavía no hay ningún número metido en el conjunto, el primero que mete (
que debería meter, pero no mete) es el 2, que no estaba en “n” porque era un conjunto vacío, así que cumple la condición de no estar en “n”.
Con la instrucción siguiente print (p) lo imprime en pantalla, apareciendo el 2.
La siguiente instrucción, n.update(range (p*p, 1000+1, p)) mete en el conjunto el valor \( p\cdot p \), que en este caso es \( 2\cdot 2=4 \), con lo cual, al ser producto de dos números ya no puede ser primo, sea 2 ó 3 ó el que sea.
Esto hace que vaya incluyendo sólo números compuestos, con lo que solamente los primos cumplirán la condición de la instrucción “if p not in n”, de forma que sólo se listarán los primos.
Vemos que en el bucle pasa eso (lo de meter los números al cuadrado) hasta 1000, y después aparece una “p” detrás; esto quiere decir que los números entran en el bucle de “p” en “p”, es decir, cuando p=2 van entrando sólo los pares, no todos los números; cuando p=3 los mete de tres en tres 9, 12, 15... No importa que no meta el 6, porque es par y ya lo metió antes
(de hecho, como dije arriba, ya metió todos los pares y en el conjunto no se repiten números, así que realidad va metiendo 9, 15... los múltiplos de 3 no pares)Y así sucesivamente.
Saludos.
