Re: Descomponer en factores primos PHP
| From: | Fernando Herrero Peletero | Date: | Sat, 17 Jan 2004 19:32:36 +0000 |
| Subject: | Re: Descomponer en factores primos PHP | ||
| References: | 1 | Groups: | php.general.es |
| Request: | Send a blank email to general-es+get-44566@lists.php.net to get a copy of this message | ||
>Hola.
Kaixo
>Estaba en casa aburrido de la vida
A veces pasa ;-)
> y se me ocurrio acer una funcion que haga lo siguiente
> calcule la raiz n de un numero X.
> Es decir la raiz cubica de un numero o la raíz cuarta, etc.
Mátematicas, qué divertido:
x = raiz r de n = n elevado a 1/r = (e elevado a ln(n)) elevado a 1/r =
e elevado a (ln(n) / r)
En php:
x = exp(log(n) / r)
Puedes comprobarlo ;-) pero te advierto que las matemáticas aplicadas son
correctas.
Nota: ln en matemáticas es logaritmo natural (base e = 2.7...) para
diferenciarlo de log que suele utilizarse como logaritmo base 10.
> Para eso antes debo descomponer el numero X en factores primos.
No entiendo porqué, es más rápido la maneta anterior, matemáticamente es la
correcta ;-)
> Y me dio por buscar una funcion que calcule todos los numeros primos q ay
asta el numero X.
Tenia un algoritmo implementado en basic para eso, de echo hice dos, uno
factorizaba (lo que pides) y otro listaba números primos...
Y este algoritmo si que es entretenido de materializar...
Pensando en cómo se resolvia en la implementación que tenia (casualidad
hacia una semana pensaba en el) he "descubierto" una forma de agilizarlo.
Para buscar los factores de n lo que hacia basicamente era recorrer de 1 a n
para ver cuales eran los divisores de n...
pero lo cierto es que el límite de búsqueda no debe de ser n sino n/x, me
explico:
1. Si n es divisible entre x, lo que tenemos que hacer ahora es
factorizar n/x y ya tenemos la solución.
2. Si n no es divisible entre x, y tiene algun divisor, forzosamente
esté se hallará entre x y n/x.
Asi pues con 1 tenemos recursividad, un poderoso recurso de programación si
se utiliza bien, y con 2 tenemos reducción de espectro de búsqueda = ahorro
de tiempo de búsqueda.
Saludos