división por tentativa es el algoritmo de factorización de enteros más sencillo y fácil de entender.- ..................................................:http://es.wikipedia.org/w/index.php?title=Especial:Libro&bookcmd=download&collection_id=cea23efb02423129c9b4d9a42cd7bf453eaafc94&writer=rdf2latex&return_to=Divisi%C3%B3n+por+tentativa
Usa la división por tentativa
La división por tentativa es de lejos la prueba más simple para determinar la primalidad. Para las cifras pequeñas, también suele ser la prueba disponible más rápidas. Este método se basa en la definición de un número primo: un número es primo si no tiene más divisores que el uno y sí mismo.
-
1Designa n como el número que quieres probar. En el método de división por tentativa para probar la primalidad, debes dividir el número dado n entre todos los factores enteros posibles. Para valores grandes de n, como n=101, no es muy práctico dividirlo entre todos los números enteros menores a n. Por suerte, existen muchos trucos para reducir significativamente el número de factores que debes probar.
Determina si n es par. Todos los números pares son divisibles entre 2. Debido a esto, si n es par puedes dar por hecho que n es compuesto y no primo. Para determinar rápidamente si un número es par, solo presta atención al último dígito. Si el último dígito es 2, 4, 6, 8 o 0, el número es par y por tanto no es primo.
- La única excepción a esta regla es el número 2 por ser primo, ya que solo es divisible entre sí mismo y el 1. El 2 es el único número primo y par.
Divide n entre todos los números ubicados en el rango de 2 y n-1. Debido a que el número primo no tiene otros factores más que el 1 y sí mismo, y a que los factores primos son necesariamente menores a sus productos; comprobar la divisibilidad de todos los números menores a n y mayores a 2 determinará si n es primo. Comenzamos con los números después de 2 porque los números pares, que son múltiplos de 2, no son primos. Este método está lejos de ser el más efectivo para esta prueba y, como se verá más adelante, existe una serie de estrategias de simplificación.
- Por ejemplo, si utilizamos este método para probar si 11 es primo o no, debemos dividir 11 entre 3, 4, 5, 6, 7, 8, 9 y 10 cada vez que busquemos un número entero sin resto como respuesta. Debido a que ninguno de estos números se divide entre 11, podemos decir que 11 es primo.
Para ahorrar tiempo, prueba solo hasta la raíz cuadrada de n, redondeada.Probar el número n con todos los números entre 2 y n -1 puede convertirse rápidamente en un proceso que demande mucho tiempo. Por ejemplo, si quieres comprobar si 103 es un número primo de esta forma, tendríamos que dividirlo entre 3, 4, 5, 6, 7, etc. ¡Hasta llegar al 102! Por suerte, no necesitas probar todos los factores posibles. En realidad, solo se requiere probar los factores entre 2 y la raíz cuadrada de n. Si la raíz cuadrada de n no es un número entero, redondéalo hasta el número entero más cercano y en su lugar prueba ese número. El siguiente ejemplo lo explicará:
- Analicemos los factores de 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2, and 100 ×1. Nota que después de 10 × 10, los factores son los mismos que aquellos antes de 10 × 10, solo se revierten. En general, nosotros podemos ignorar los factores de n mayores a su raíz cuadrada, ya que estos no son más que los factores menores a la raíz cuadrada de n reorganizados.
- Veamos este problema. Si n =37, no necesitamos probar todos los números desde 3 hasta 36 para determinar si n es primo. En su lugar, solo tenemos que probar los números desde 2 hasta la raíz cuadrada de 37, redondeada.
- La raíz cuadrada de 37 es 6.08 que redondeamos a 7.
- 37 no es divisible entre 3, 4, 5, 6 y 7, por lo que podemos determinar con certeza que es primo .
No hay comentarios:
Publicar un comentario