Este ya es un problema más matemático, lo primero es buscar información acerca de los números primos. La definición matemática de los números primos es: son aquellos números que solo son divisibles exactamente entre la unidad y entre sí mismos, a partir de esta definición comenzaremos. La solución más sencilla que podría encontrar el programador es consultar un texto de matemática que tenga los números primos y escribirlos, utilizando la computadora como maquina de escribir, sin embargo, a pesar de la cerrado de la solución es una buena salida del problema:
Primos 1
|
Program primos_1; Begin Writeln(' Los Números primos son: 2, 3, 5, 7, 11, 13... '); End. |
main() { printf(" Los Números primos son: 2, 3, 5, 7, 11, 13 ... \n "); } |
print *, 'Los Números Primos son: 2, 3, 5, 7, 11, 13 ...' end
|
Como se puede observar este programa es cerrado, ya que no permite listar más números primos. Si el cliente no esta conforme con este programa, puede solicitar los números primos para un intervalo dado. Para ello, el programador utiliza la definición de los números primos y el hecho de que en una división exacta el residuo es cero. El código para una solución es el que sigue:
Primos 2
|
program primos_2; var divisor, primo, min, max:integer; begin divisor:=1; write (' Borde inferior del intervalo: '); readln (min); write (' Borde superior del intervalo: '); readln (max); for primo := min to max do begin divisor = 1; repeat divisor:=divisor + 1; until ((primo)MOD(divisor)<>0); if (primo=divisor) writeln ('Primo ',primo); end; end. |
main() { int divisor=1, primo, min, max; printf (" Borde inferior del intervalo: "); scanf ("%d",&min); printf (" Borde superior del intervalo: "); scanf ("%d",&max); for (primo = min; primo <= max; primo++){ divisor = 1; do { divisor++; } while ((primo)%(divisor)!=0); if (primo==divisor) printf ("Primo %d \n", primo); }; } |
integer divisor, primo, min, max, band print *,' Borde inferior del intervalo: ' read *,min print *,' Borde superior del intervalo: ' read *,max do 10 primo = min, max, 1 divisor = 1 band = 1 do while (band .eq. 1) divisor = divisor + 1 if ((primo/divisor - (primo*1.0)/(divisor*1.0)) .eq. 0.0) then band = 0 end if end do if (primo .EQ. divisor) then print *,'Primo ', primo end if 10 continue end |
Esta solución solicita los limites superior e inferior del intervalo, luego para cada uno de los números dentro del intervalo comienza a probar su división con un divisor que comienza en dos y se incrementa, hasta encontrar que la división sea exacta, si al encontrar la división exacta el divisor es igual que el número a probar, este número es un número primo.
Observen el código para Fortran, la función que extrae el residuo de una división exacta no esta en las librerías de Fortran, por lo que la construimos, en Fortran la división de dos números enteros nos da un entero, es decir, omite el residuo, así que si a esta división entera le restamos una división real, que sí da decimales, podemos simular la función de extraer el residuo, ya que cuando ambas son iguales su diferencia es cero, y la división es exacta.
Podemos observar que de esta manera podemos obtener los números primos en cualquier intervalo que deseemos, lo que lo hace más versátil y abierto que el primer ejemplo, sin embargo tiene una falla, si se introduce como borde inferior un numero menor que dos entrara en un lazo de repetición infinito, para poder detener el programa si esto ocurre se deben presionar las teclas ctrl +c simultáneamente. La corrección de esta falla aparece en el siguiente código:
Primos 3
|
program primos_3; var divisor, primo, min, max:integer; begin write (' Borde inferior del intervalo: '); readln (min); if (min < 2) then min := 2; write (' Borde superior del intervalo: '); readln (max); for primo := min to max begin divisor = 1; repeat divisor:=divisor+1; until ((primo)MOD(divisor)<>0); if (primo=divisor) then writeln ('Primo ', primo); end; end. |
main() { int divisor=1, primo, min, max; printf (" Borde inferior del intervalo: "); scanf ("%d",&min); if (min < 2) min = 2; printf (" Borde superior del intervalo: "); scanf ("%d",&max); for (primo = min; primo <= max; primo++){ divisor = 1; do { divisor++; } while ((primo)%(divisor)!=0); if (primo==divisor) printf ("Primo %d \n", primo); }; } |
integer divisor, primo, min, max, band print *,' Borde inferior del intervalo: ' read *,min if (min .lt. 2) then min = 2 end if print *,' Borde superior del intervalo: ' read *,max do 10 primo = min, max, 1 divisor = 1 band = 1 do while (band .eq. 1) divisor = divisor + 1 if ((primo/divisor - (primo*1.0)/(divisor*1.0)) .eq. 0.0) then band = 0 end if end do if (primo .EQ. divisor) then print *,'Primo ', primo end if 10 continue end |
Ahora el cliente quiere que le resuelvan el problema de conseguir los N primeros números primos, ya que en el ejemplo anterior no se cuantifican los números primos encontrados. El programador no sabe en que intervalo encontrara una determinada cantidad de números primos, por lo que el programa anterior no le sirve, debiendo pensar nuevamente, encontrando como posible solución:
Primos 4
|
program primos_4; var divisor, primo, cont_primo, max:integer; begin divisor:=1 ; primo:=3; cont_primo:=1; write (' Cuantos Números Primos: '); readln (max); writeln (' Primo No. 1 = 2 '); repeat begin repeat divisor := divisor + 2; until ((primo)MOD(divisor) <> 0); if (primo = divisor) then begin cont_primo:=cont_primo+1; writeln (' Primo No. ',cont_primo,' = ',primo); end primo :=primo + 2; divisor := 1; end until (cont_primo < max); end. |
main() { int divisor = 1, primo = 3, cont_primo = 1, max; printf (" Cuantos Números Primos: "); scanf ("%d", &max); printf (" Primo No. 1 = 2 \n"); do { do { divisor += 2; } while ((primo) % (divisor) != 0); if ( primo == divisor ) { cont_primo ++; printf (" Primo No. %d = %d \n",cont_primo,primo); }; primo += 2; divisor = 1; } while (cont_primo < max); } |
integer divisor, primo, cont_primo, max, band1, band2 print *,' Cantidad de Números primos: ' read *,max band1 = 1 primo = 1 print *,'Primo No. 1 = 2' cont_primo = 1 do while (band1 .eq. 1) divisor = 1 band2 = 1 primo = primo + 2 do while (band2 .eq. 1) divisor = divisor + 2 if ((primo/divisor - (primo*1.0)/(divisor*1.0)) .eq. 0.0) then band2 = 0 end if end do if (primo .EQ. divisor) then cont_primo = cont_primo + 1 print *,'Primo No.',cont_primo,' = ', primo end if if ( cont_primo .eq. max) then band1 = 0 end if end do end |
Este algoritmo solicita la cantidad de números primos que se desean obtener, los calcula de una forma similar al algoritmo anterior, al encontrar uno incrementa un contador y termina de buscar cuando el contador es igual a la cantidad de números primos deseados. Para calcular los números primos, este algoritmo asume que el número dos ya es el primer primo, por lo que tanto el número sospechoso se puede incrementar en dos, al igual que el divisor, siendo estos siempre impares, y se omiten el resto de números pares, lo cual reduce a la mitad el tiempo de búsqueda de los números primos, y por ende el de ejecución del programa. En programas grandes donde el tiempo de ejecución cuenta, es necesario optimizar nuestro código a fin de reducir el tiempo de ejecución lo más posible.
|
Primos 1 |
Al programador no le tomo mas de cinco minutos de su tiempo realizar este programa, sin embrago debió consultar cuáles eran los números primos, por lo que el tiempo total de realización del programa fue de aproximadamente 15 minutos. El programa es el más rápido, sin embargo no permite ver mas números primos |
|
|
Primos 2 |
Este algoritmo permite calcular los números primos que hay en un intervalo determinado, por lo que es más general que el anterior. El programador debió consultar un poco más de tiempo ya que no se puede aprender todos los números primos, tuvo que aprender a calcularlos, después dedico cerca de 30 minutos sólo a transcribir el programa, el tiempo total de realización del programa es de aproximadamente una hora, elevando considerablemente el costo del programa. El algoritmo para verificar si un número A es primo implica A divisiones, lo que lo hace lento si el número A es grande, además puede ocasionar un error si se introduce como limite inferior un número menor que dos, ya que el número uno no es divisible exactamente con ningún otro número, por lo que el programa repetirá la búsqueda hasta ocasionar un error de desbordamiento conocido como número fuera de rango. |
|
|
Primos 3 |
El programador debió invertir el mismo tiempo que el algoritmo anterior, además del necesario para encontrar el error del limite inferior igual a uno, y corregirlo, esto incrementa el tiempo de realización en unos 10 minutos, elevando su precio. Sin embargo tiene el mismo problema del tiempo de ejecución para números grandes. |
|
|
Primos 4 |
Colocar un contador y modificar el ciclo de repetición al algoritmo de búsqueda del número primo utilizado anteriormente no toma más de 15 minutos, pero reducir a la mitad el tiempo de ejecución del programa le tomo al programador cerca de 30 minutos extras. Con un tiempo total de realización de dos horas es un programa costoso, comparado con los anteriores. |
|
|
Estos algoritmos de búsqueda de números primos aun pueden ser mejorados, se puede reducir el tiempo de ejecución considerablemente, para ello es necesario invertir un poco más de tiempo de realización del programa. Nótese que los algoritmos aquí mostrados han evolucionado de acuerdo a la información que se halla recolectado, cuanto más información obtuvimos sobre el calculo de números primos, mejor ha sido el algoritmo para su búsqueda. Esto puede conducir a una regla fundamental en programación: Cuanto más sabemos del problema y su solución, mejor será el algoritmo Esto es fundamental, ya que el programador debe actuar como maestro a la computadora, debe explicarle en detalle como esta va a resolver el problema. Es muy común que luego de haber hecho un programa determinado, el programador domine mucho más el problema que hasta el mismo cliente o usuario final. |
||