Este siguiente algoritmo lo escribí para un trabajo en Pascal:
PROGRAM PrimeNumber;
USES crt; {esto lo pongo por si acaso... yo nunca lo usé}
VAR
x: Integer;
i: Integer;
limit: Real;
isPrime: Boolean;
BEGIN
Write ('Ingrese un número para averiguar si es primo: ');
ReadLn (x); {leemos el número}
limit:=sqrt(x); {elegimos el límite del ciclo: raíz² de x}
IF ((x mod 2)=0)
THEN isPrime:=False {si x es par, no es primo}
ELSE BEGIN {si x es impar, analizamos...}
i:=3; {comenzamos con el primer impar, i=3}
REPEAT
isPrime:=NOT((x mod i)=0); {x es primo si xłi}
i:=i+2 {pasamos al siguiente impar}
UNTIL (NOT(isPrime) OR (i>limit))
END; {finaliza el ciclo: x|i ó i>x^(1/2)}
IF isPrime
THEN WriteLn ('El número ingresado es ¡primo!')
ELSE WriteLn ('El número ingresado ¡no es primo!')
END.
# Nota: esto lo 'releaso' sin licencia, pueden hacer lo que les cante con eso... aunque 5 minutos (+2 de optimización) de código no puede servirles de mucho...
Este programita averigua si el número X es primo. Nada más. No informa sobre la cantidad de factores ni nada (tengo otro que sí lo hace, y es ultra copeishon!!!)
Cuando nos dieron este trabajo, el primer flaco que se mandó al pizarrón a escribir el algoritmo ─después de 3 segundos de reflexión─, se mandó una solución buena, pero no óptima: funcionaba, pero el ciclo de división calculaba por cada número desde 2 hasta X-1. Horriblemente ineficiente.
Entonces alguien ─probablemente yo─ dijo: mejor si sólo calculamos hasta la mitad de X, ya que obviamente X no puede dividirse por un número mayor que su mitad ─el resultado de tal división daría un número mayor que 1 y menor que 2 (rango de reales no enteros). Y la cosa mejoró, pero aún faltaba.
El chiste, como ya es obvio a esta altura (1.80), es la raíz cuadrada de un número. Porque los divisores mayores a esa raíz complementan a los divisores menores ─y fíjense que evité la palabra FACTOR acá.
Explico: si tomamos 36, vemos que su raíz cuadrada es 6. Esto significa que sus divisores menores que 6 (2, 3, 4) complementan a los mayores (18, 12, 9), ya que 2×18=3×12=4×9=36. Fácil. No hace falta decir que 6 se complementa con 6... ¿no?
Y como 18, 12, 9 y 4 son números compuestos, vemos que todos los factores de 36 (2 y 3) son menores que su raíz: 2<3<6 (2²3²=36.)
La idea de mejorar el algoritmo de esta manera me vino pelotudeando con integrales de ecuaciones cuadráticas (unos días después de esa clase.) Más allá de que en la clase un profesor dijo: "pero no tiene sentido dividir por números no primos, como 9 o 15, es mejor dividir sólo por primos!" ¡Pero che! ¡Pensá un poquito, grone! Una lista de CASES por cada número primo que se me ocurra hasta quichicientos es IMPOSIBLE, y el programa resultado tendría 400.000.000 de líneas de código. Además, el VERDADERO cálculo lo estaría haciendo yo, no el procesador.
Me importa poco lo que diga, porque yo ya probé el binario mil veces (corroborado con el que sí devuelve divisores), y calcular la primacidad ─¿así se dice?─ de un número mayor a 4 mil millones demora 2 de milésimas de segundo con este programa... ¡NO ME JODÁS LAS PELOTAS!
PS: Yo nunca soy de escribir primero en pseudocódigo y después pasarlo a Pascal. De hecho, en el proyecto (que nos obligaron a documentar y a mostrar el algoritmo no-Pascal) lo hice al revés: primero escribí el código en Pascal, depués hice las pruebas, y después lo pasé a pseudo... ¡¡sí, soy un trucho!!!
Bueno, me despido... se me ocurrió subir eso... porque quería escribir sobre la opinión de Steve Ballmer (CEO de Microsoft) sobre "Linux es un virus" y explicar por qué no está 'del todo' errado... Pero debido a que necesitaba más información sobre las licencias del tipo BSD decidí investigar un poco y dejarlo para otra vez... Entonces abrí la carpeta de trabajos en Pas, y me acordé del del primo (los matemáticos me resultan especialmente curiosos) y dije... WHY THE FUCK NOT? Nah... no lo dije, pero casi seguro que lo pensé...
Bueno, me te tomo el palo, saludos!
CHAU!
PS2: Si se les ocurra alguna manera de optimizarlo más, avisen.
PS3: No me refiero a optimizar como "mejor hacelo en C++ o en FORTRAN, NABO!"...
PS4: Aviso que PS acá no significa PlayStation... pero viendo tanto PSx me pareció necesario aclararlo...
