Retos PHP

Encaramos la llegada de los primeros fríos invernales con un nuevo reto PHP, está vez se trata de obtener un algoritmo que nos diga (con 100% de seguridad, nada de probabilidades) si un número (sea cual sea el tamaño) es primo o no.

El reto consiste en crear una función a la que pasamos una cadena con un número, y nos devuelve true (en caso que sea primo) o false (en caso que no sea primo). Tened en cuenta que el número que le pasemos puede tener cualquier tamaño, así que ya podéis echar mano de las librerías que hay en php para manejo de grandes números.

En esta ocasión ganará el algoritmo que devuelva el resultado correcto en el menor tiempo posible (la batería de pruebas cubrirá números pequeños, grandes, etc...).

• Fecha Límite: 1 de Diciembre

Suerte y al lío.

PD: No se pueden utilizar funciones que hagan el trabajo por nosotros, como por ejemplo "gmp_prob_prime" o "gmp_nextprime".

Hola a todos, compañeros y amigos....después de un mes de intriga e incertidumbre, aquí llegamos con los resultados del 1º Reto PHP del Rincón de Tolito.

La participación ha sido bastante más alta de lo esperado...como podéis ver en los comentarios del reto (además de los que me lo habéis enviado al correo). Así que sin más preámbulos vamos a por los resultados.

PREMIO A LA BREVEDAD

Para Víctor con 63 caracteres:

function reto($n){for($i=$n;$i;$i--)($n%$i)||$a[]=$i;return$a;}

PREMIO A LA VELOCIDAD

Para Guti (al que quiero felicitar desde aquí por su blog, y por el algoritmo) con este algoritmo:

function reto($piNumero)
{
  $aRes=array($piNumero);
  for ($iDivisor=$piNumero>>1; $iDivisor>0; $iDivisor--)
  {
    if (!($piNumero % $iDivisor))
    {
      array_push($aRes, $iDivisor);
    }
  }
  return($aRes);
}

VERSIÓN PROPIA

Yo, aunque no participo en el concurso, he desarrollado un algoritmo que, aunque no es la panacea, si que mejora infinitamente el tiempo de respuesta (en números grandes la mejora es muy notable). Lo que hace es recorrer el bucle for entre 0 y la raíz del número, con lo cual nos ahorramos muchas pasadas por el bucle, aquí os dejo el algoritmo desarrollado:

function reto($x)
{
  $t=ceil(sqrt($x));
  if ($t*$t==$x)
    $d[]=$t;
  for ($n=1;$n<$t;$n++)
  {
    if (!($x%$n))
    {
      $d[]=$n;
      $d[]=$x/$n;        
    }
  }
  return $d;
}

Un saludo a todos

Nota: Guti ha enviado una versión que precalculaba las factorizaciones de todos los números indicados y los guardaba en un archivo (unos 500 Gb(para el rango de enteros de php) calcula él que ocuparía). Yo la verdad no tengo espacio en disco suficiente para probarlo (ni paciencia para generar el archivo que precalcula los datos), pero creo que la búsqueda de un número en un archivo de texto de 500 Gb no debe ser una cosa muy rápida.

Hoy desde "El Rincón de Tolito" inauguramos una nueva sección: "RETOS PHP", la idea es la siguiente: yo(podéis enviarme ideas para nuevos retos) propongo desde aquí un reto con sus condiciones, y vosotros vais enviándome vuestras soluciones en forma de comentario del post (los comentarios están moderados, y por tanto no aparecerán publicados hasta el final del concurso), o por correo electrónico (tolito(arroba)gmail(dot)com). Una vez terminado el plazo publicaré los códigos ganadores, así como sus autores. Así que vamos al lío con el primer reto:

Enunciado: Desarrollar una función llamada "reto" a la cual la pasemos un número (integer) y nos devuelva un array (divisor[0]=x....divisor[n]=y) con todos los divisores de dicho número, incluyendo el 1 y el propio número.

Códigos Ganadores: Hay 2 premios:

• Código veloz: Después de una batería de pruebas(serán las mismas para todos) se verá cual es el código más rápido de todos los participantes.
• Código breve: Este premio se lo llevará el código que menos ocupe, así que a abreviar...

Condiciones:

• Las pruebas se llevarán a cabo en un servidor Ubuntu con Apache y PHP 5.2.5.
• Cada usuario puede enviar 2 programas, así puede optar a los 2 premios a la vez, ya que es complicado que el mismo código gane los 2 premios, aunque nunca se sabe...
• El envío debe incluir el nick del autor, una dirección de correo electrónico (no se hará publica para evitar spameos), y el código de la función.
• Fecha límite para el envío de respuestas: 30 de Septiembre del 2009
• El código que no funcione, o que de errores no será considerado valido. Puede dar warnings o notice siempre que funcione correctamente

¡Animo a todos y a optimizar código!

Actualización [28 Agosto 2009 - 14:41]: Ya hemos recibido los primeros programas...

Actualización [01 Septiembre 2009 - 10:50]: Siguen llegando programas, pero todos son para el premio de brevedad...a ver si alguien se anima a optimizar el código para mejorar su rendimiento.

Actualización [02 Septiembre 2009 -19:21]: En el premio a la brevedad solo se tendrá en cuenta la función, no os preocupeis de etiquetas php y demás historias...