-- Generador de primos. Jaime Soffer, Mayo 2007.
-------------------------------------------------------------
 
-- Raí­z cuadrada para enteros (composición de funciones)
isqrt = floor.sqrt.fromIntegral
 
-- Predicado: Verdadero si algún elemento
-- en la lista (x:xs) divide a n
 
dividep [] n rn = False
 
dividep (x:xs) n rn =
 
-- "Optimizado" para "algún elemento en la lista menor que |n^(1/2)|" 
-- (no cambia el orden asintótico)
-- (x < |n^(1/2)| <=> x*x < n; x, n son enteros positivos)
 
  -- if ((((x*x) < n)||((x*x) == n)) && (mod n x == 0))
 
  -- Optimización: almacenar sqrt(n)
  -- El ganador; 20% de ganancia en tiempo comparado con usar x*x,
  -- por el valor almacenado
  if (((x < rn)||(x == rn)) && (mod n x == 0))
  -- Lento: calcula sobre todos los primos menores a n
  -- if (mod n x == 0)
   then True
   else dividep xs n rn
 
-- Inicia con una lista vací­a y el primer primo (2). Para cada
-- entero n mayor que 2, primero decide si los primos menores
-- a n lo dividen.
-- Si es así­ ignora al elemento y regresa los primos de n+1.
-- En otro caso agrega n y devuelve los primos de n+1
-- tomando en cuenta que n es primo.
 
primos (x, n) =
  if dividep x n (isqrt n)
   then primos (x, (n+1))
   else n:primos ((x++[n]), (n+1))
 
-- Usar (x++[n]) parece mas lento que (n:x) porque hay que
-- recorrer la lista para la inserción, pero dividep depende de que
-- los elementos entren en orden (no es posible hacer n:x sin afectar
-- la rutina de comparación con sqrt n).
 
--------------------------------------------------------------