No es muy difícil preparar un programa casero de cálculo de los números primos. Como se ha comentado se puede hacer con operaciones normales. Lo que sí pasa es que no hay una fórmula, sino un proceso o heurística; o lo que es lo mismo, se requiere un algoritmo y, por ello, para llevarlo a la práctica, un programa de cálculo numérico.
Aquí presento un algoritmo muy simple y de andar por casa. No es ni muy elegante ni muy eficiente en tiempo de cálculo, y creo que tampoco en exactitud para números grandes, por lo que luego explicaré. Pero creo que sí tiene la virtud de ser bastante inteligible por aproximarse a la definición académica de número primo. Lo presento como simple curiosidad, experimento o material académico para quien le pudiera interesar.
La base es muy simple. Lo explico primero verbalmente. Se trata de partir de la definición de número primo. Si N es un número primo sólo será divisible entre 1 y N. El programa crea un bucle infinito donde va tratando sucesívamente números N, N+1, N+2... Y para cada número N realiza las sucesivas divisiones entre N/2, N/3,... N/N-1, comprobando si alguna de esas divisiones es entera (no hay decimales). En cuanto detecta una sola división entera quiere decir que el número no es primo y pasa al siguiente. Si todas las divisiones con los divisores 2, 3, ... N-1 resultan con decimales (no enteras) quiere decir que el número en cuestión sólo es divisible por 1 y por N. En consecuencia es un número primo. Se imprime en pantalla y se se pasa al siguiente N+1, volviendo a repetir el cálculo. Y así va imprimiendo todos los números primos (los tres primeros 1,2 y 3 se imprimen a mano y se calcula a partir de 4).
Como ya ha dicho alguien por ahí, en realidad no hay porque calcularlos todos, pues hay hay una lista suficientemente grande de números primos calculados y si se necesitan para una aplicación basta con tomarlos de esas listas. Sólo tiene sentido calcular a partir del más grande que se haya calculado hasta ahora, y para éso hay muchos mejores algoritmos eficientes de profesionales matemáticos y programadores. Y programas expresos no en lenguaje de alto nivel que pueden usar un nº pequeño de bytes para almacenar números decimales, sino en ensamblador haciendo las operaciones directamente en sistema binario y empleando muchísimos más bytes para almacenar números que los que usan los lenguajes estándar. De forma que los cálculos sean más exactos y no se produzcan errores por redondeo u overflow.
Bueno, pues presento este pequeño divertimento académico, que ni siquiera puede llamarse aplicación. He preparado primero un diagrama de flujo -en imagen- para que se entienda mejor lo que pretendo hacer. Luego un script en pseudocódigo, para que se pueda adecuar a cada lenguaje concreto y, finalmente una implementación en BASIC256.
La variable que representa N la he llamado 'numero' y los sucesivos valores desde 2... hasta N-1 que toman los sucesivos divisores los he colocado en una variable 'divisor'. Sin embargo se verá que, en principio, los tomo como float (o double según el lenguaje) y es por una razón. Los valores enteros como tales pueden, según el lenguaje y el tipo, oscilar entre 256 o 32768, y si se quieren calcular valores de primos muy altos no valdrán. Así que he colocado variables en doble precisión que aunque en principio estén pensados para números decimales, pueden usarse como enteros y hacer cálculos con números más grandes. De todas formas otro de los posibles defectos del algoritmo es que no sé como se comportará para números muy grandes por defectos de redondeo. Además se usa una bandera como valor booleano, que yo he llamado 'esprimo'. El valor true es 1 y el valor false es 0.
Tanto el pseudocódigo como el código BASIC256 no son nada elegantes, mucho IF y GOTO que puede despistar, y podrían resolverse con otro tipo de estructuras tipo FOR... NEXT, DO... WHILE, etc. Pero a cambio siguen fielmente el diagrama de flujo que creo que sí se entiende bastante bien. Además si se emplean otras estructuras de bucle (si alguien quiere programarlo de otra manera) habrá que tener cuidado de romper el bucle en cuanto se cumpla condición de no-primo. Tal y como yo lo he programado se parte de que el número a estudiar es en principio primo (esprimo = 1 = true) mientras no se demuestre lo contrario. Pero en cuanto se produce el cambio de bandera de 1 a 0, automáticamente se para el proceso, se incremente el valor de 'numero' (N) y no se sigue examinado. Si por ejemplo se usa un bucle for... next desde 2 hasta N-1, imagínese que se está estudiando el nº 1.600.000, haciendo sucesivas divisiones por 2, 3, 4... 1.599.599. Es una pérdida de tiempo, pues ya en la primera división por 2 se ve que el resto es 0, el número es no-primo y no hace falta seguir. Así que si se utilizan estructuras for... next o do... while habrá que prever su aborto para no perder tiempo. Por eso el método que yo he utilizado con if y goto, aunque sea poco elegante, prima la eficiencia, creo.
Por último comentar que el programa en BASIC256 lo he testado con
https://numeros.xyz/numeros-primos/y me ha dado correcto hasta el 541 (no he seguido). Es cuestión de calcular más rato y molestarse en comprobar. También modificando el valor de inicio de la variable 'numero' que en el programa se inicializa en 4 se puede empezar a calcular a partir de valores mayores y testar con esa u otras páginas.
Bueno, pues sin más dejo el material. En el programa en BASIC256, al no hacer falta declarar variables, he sustituido por REM las mismas.
El pseudocódigo:
1. declarar numero como variable de doble precisión
2. declarar esprimo como variable booleana
3. declarar divisor como varable de doble precisión
4. imprimir 1
5. imprimir 2
6. imprimir 3
7. numero = 4
8. divisor = 2
9. esprimo = verdadero
10. si (numero / divisor) - parte_entera(numero / divisor) = 0 ir a 16
11. divisor = divisor + 1
12. si divisor < numero volver a 9
13. si esprimo = falso ir a 14.
14. imprimir numero
15. numero = numero + 1
16 volver a 8.
17. esprimo = falso
18. ir a 12.
El programa BASIC256:
rem numero es el que se desea saber si es primo
rem esprimo es bandera =1 es primo =0 no lo es
rem divisor sucesivos divisores de 2 hasta numero
numero = 4
etiq8: divisor = 2
etiq9: esprimo = 1
IF (numero
/divisor
) - INT(numero
/divisor
) = 0 THEN GOTO etiq17
divisor = divisor + 1
IF divisor < numero THEN GOTO etiq9
IF esprimo = 0 THEN GOTO etiq15
etiq15: numero = numero + 1
GOTO etiq8
etiq17: esprimo = 0
GOTO etiq15