Discusión:División por tentativa

Último comentario: hace 15 años por Sabbut en el tema Algoritmo

Contraejemplo

editar

Hay un contraejemplo: 43 = 2 * 23, y 23 es mayor que la raiz de 23.

Esa cota es para la construccion de una criba de eratostenes donde no puede aparecer un numero compuesto mayor que la raiz de n, tal que no es multiplo de algun numero menor que la raiz de n.

Para hallar esto la cota si no me equivoco es n/2. — El comentario anterior es obra de 83.57.37.62 (disc. · contr. · bloq.), quien olvidó u omitió firmarlo.   18:44 3 ago 2008 (UTC)Responder

Respuesta

editar

Esa cota es correcta. De hecho, tu contraejemplo no es un contraejemplo, porque  . Aunque, si nos ponemos estrictos,   Así que más bien es  . Más bien Lo que debes de tomar en cuenta es que si   es un número compuesto, entonces al menos un factor tiene que ser menor o igual que su raíz cuadrada. Y si no me crees, aquí tienes la demostración matemática que puedes encontrar en cualquier libro de teoría de números:

Teorema Si   es un número entero que no es divisible por ningún número entero menor o igual que  , entonces   debe ser un número primo.

Demostración: La demostración es por reducción al absurdo. Supongamos que el teorema es falso, es decir, que   no es divisible por ningún entero menor o igual que   pero que   no es un número primo.

Como   no es primo, entonces lo podemos factorizar como  . Además, como   no tiene factores primos menores o iguales que  , entonces tampoco los tienen   y   y además ellos mismos son mayores que  . Pero como  , entonces estaríamos diciendo que  , es decir, que  , lo cual es absurdo.

Por lo tanto el teorema no puede ser falso (es decir, es verdadero).

  18:44 3 ago 2008 (UTC)Responder

Malentendido

editar

Disculpa, error mio entonces. Entendi que deberia dividirse entre todo numero primo menor que la raiz de n. Es cierto que al menos un primo ha de ser menor que la raiz cuadrada. Pero en ese caso supongo que tienes que despues de dividir has de repetir el proceso con n/(p1*p2*...*pn), donde pn son los primos por los que has dividido. puede ser? Siguiendo con el ejemplo 46 = 2 * 23, para hallar el 23.

No estoy seguro de si el articulo lo explica, pero si fuese asi, seria conveniente poner un ejemplo de la iteracion, para no dejar lugar a dudas.

Un saludo y gracias por tu trabajo. — El comentario anterior es obra de 83.57.37.62 (disc. · contr. · bloq.), quien olvidó u omitió firmarlo.   13:36 6 ago 2008 (UTC)Responder

Propuesta

editar

Mejoraré el artículo cuando tenga tiempo. Pero no será pronto.   13:36 6 ago 2008 (UTC)Responder

Algoritmo

editar

Dejo aquí una parte que estaba en número primo pero que igual queda mejor aquí:

A la hora de construir un algoritmo informático, no es necesario calcular explícitamente la raíz cuadrada, sino que se puede parar en cuando uno vea que el cociente es menor que el divisor. Concretamente, la última posibilidad de que N sea compuesto es dividirlo por un m primo tal que m+1 al cuadrado es mayor que N.

A lo mejor lo acabo aprovechando, a lo mejor no. Sabbut (めーる) 07:48 16 abr 2009 (UTC)Responder

Volver a la página «División por tentativa».