Numeros primos grandes
Páginas: 10 (2320 palabras)
Publicado: 1 de abril de 2013
Números Primos
Un número primo es un número entero mayor que cero, que tiene exactamente dos divisores positivos. También podemos definirlo como aquel número entero positivo que no puede expresarse como producto de dos números enteros positivos más pequeños que él, o bien, como producto de dos enteros positivos de más de una forma. Conviene observar que con cualquiera de las dosdefiniciones el 1 queda excluido del conjunto de los números primos.
Ejemplos: a) El 7 es primo. Sus únicos divisores son 1 y 7. Sólo puede expresarse como producto de 7·1.
b) El 15 no es primo. Sus divisores son 1, 3, 5 y 15. Puede expresarse como 3·5. (y también como 15·1)
El término primo no significa que sean parientes de alguien. Deriva del latín "primus" que significaprimero (protos en griego). El teorema fundamental de la aritmética afirma que todo número entero se expresa de forma única como producto de números primos. Por eso se les considera los "primeros", porque a partir de ellos obtenemos todos los demás números enteros. (El 15 se obtiene multiplicando los primos 3 y 5)
Los 25 primeros números primos son 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 y 97, que son todos los primos menores que 100.
Cómo averiguar si un número es primo.
El algoritmo más sencillo que puede utilizarse para saber si un número n es primo es el de la división. Se trata de ir probando para ver si tiene algún divisor propio. Para ello vamos dividiendo el número n entre 2, 3, 4, 5, ... , n-1. Si alguna de lasdivisiones es exacta (da resto cero) podemos asegurar que el número n es compuesto. Si ninguna de estas divisiones es exacta, el número n es primo. Este método puede hacerse más eficiente observando simplemente, que si un número es compuesto alguno de sus factores (sin contar el 1) debe ser menor o igual que √ n. Por lo tanto, el número de divisiones a realizar es mucho menor. Sólo hay que dividir entre 2,3, 4, 5, ... , [√ n]. En realidad, bastaría hacer las divisiones entre los números primos menores o iguales que √ n.
Ejemplo: Para probar que 227 es primo sabiendo que √227 = 15'0665... basta con ver que no es divisible entre 2, 3, 5, 7, 11 y 13.
Este procedimiento resulta eficiente para números pequeños o que tienen factores pequeños. Sin embargo si el número tiene por ejemplo unas 20cifras y es primo, habrá que realizar miles de millones de divisiones para comprobarlo. Aunque un ordenador pueda realizar millones de divisiones en un segundo, el tiempo necesario es bastante considerable. Y cuando el número de dígitos aumenta, el tiempo necesario, crece de forma exponencial.
Historia de los números primos
Pitágoras
Distinguieronconceptos tales como los de número primo ó numero perfecto (aquél que la suma de sus divisores propios da como resultado el número en sí mismo; por ejemplo, el 28). La influencia de la escuela pitagórica es indudable sobre los Elementos de Euclides.
Euclides
Cuando aparecieron los Elementos Euclidianos ya habían sido probados varios resultados importantes acerca de números primos. Euclides demuestraque hay infinidad de números primos en la proposición número 20 del libro IX de los Elementos: “Ningún conjunto de números primos incluye a todos”.
Eratóstenes
Cerca del 200 a. C., el astrónomo Eratóstenes de Cirene ideó un algoritmo para calcular números primos llamado Criba ó Tamiz de Eratóstenes.: La criba de Eratóstenes es un algoritmo que permite hallar todos los números primos menores queun número natural dado N. Se forma una tabla con todos los números naturales comprendidos entre 2 y N y se van tachando los números que no son primos de la siguiente manera: cuando se encuentra un entero que no ha sido tachado, ese número es declarado primo, y se procede a tachar todos sus múltiplos. El proceso termina cuando el cuadrado del mayor número confirmado como primo es mayor que N....
Un número primo es un número entero mayor que cero, que tiene exactamente dos divisores positivos. También podemos definirlo como aquel número entero positivo que no puede expresarse como producto de dos números enteros positivos más pequeños que él, o bien, como producto de dos enteros positivos de más de una forma. Conviene observar que con cualquiera de las dosdefiniciones el 1 queda excluido del conjunto de los números primos.
Ejemplos: a) El 7 es primo. Sus únicos divisores son 1 y 7. Sólo puede expresarse como producto de 7·1.
b) El 15 no es primo. Sus divisores son 1, 3, 5 y 15. Puede expresarse como 3·5. (y también como 15·1)
El término primo no significa que sean parientes de alguien. Deriva del latín "primus" que significaprimero (protos en griego). El teorema fundamental de la aritmética afirma que todo número entero se expresa de forma única como producto de números primos. Por eso se les considera los "primeros", porque a partir de ellos obtenemos todos los demás números enteros. (El 15 se obtiene multiplicando los primos 3 y 5)
Los 25 primeros números primos son 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 y 97, que son todos los primos menores que 100.
Cómo averiguar si un número es primo.
El algoritmo más sencillo que puede utilizarse para saber si un número n es primo es el de la división. Se trata de ir probando para ver si tiene algún divisor propio. Para ello vamos dividiendo el número n entre 2, 3, 4, 5, ... , n-1. Si alguna de lasdivisiones es exacta (da resto cero) podemos asegurar que el número n es compuesto. Si ninguna de estas divisiones es exacta, el número n es primo. Este método puede hacerse más eficiente observando simplemente, que si un número es compuesto alguno de sus factores (sin contar el 1) debe ser menor o igual que √ n. Por lo tanto, el número de divisiones a realizar es mucho menor. Sólo hay que dividir entre 2,3, 4, 5, ... , [√ n]. En realidad, bastaría hacer las divisiones entre los números primos menores o iguales que √ n.
Ejemplo: Para probar que 227 es primo sabiendo que √227 = 15'0665... basta con ver que no es divisible entre 2, 3, 5, 7, 11 y 13.
Este procedimiento resulta eficiente para números pequeños o que tienen factores pequeños. Sin embargo si el número tiene por ejemplo unas 20cifras y es primo, habrá que realizar miles de millones de divisiones para comprobarlo. Aunque un ordenador pueda realizar millones de divisiones en un segundo, el tiempo necesario es bastante considerable. Y cuando el número de dígitos aumenta, el tiempo necesario, crece de forma exponencial.
Historia de los números primos
Pitágoras
Distinguieronconceptos tales como los de número primo ó numero perfecto (aquél que la suma de sus divisores propios da como resultado el número en sí mismo; por ejemplo, el 28). La influencia de la escuela pitagórica es indudable sobre los Elementos de Euclides.
Euclides
Cuando aparecieron los Elementos Euclidianos ya habían sido probados varios resultados importantes acerca de números primos. Euclides demuestraque hay infinidad de números primos en la proposición número 20 del libro IX de los Elementos: “Ningún conjunto de números primos incluye a todos”.
Eratóstenes
Cerca del 200 a. C., el astrónomo Eratóstenes de Cirene ideó un algoritmo para calcular números primos llamado Criba ó Tamiz de Eratóstenes.: La criba de Eratóstenes es un algoritmo que permite hallar todos los números primos menores queun número natural dado N. Se forma una tabla con todos los números naturales comprendidos entre 2 y N y se van tachando los números que no son primos de la siguiente manera: cuando se encuentra un entero que no ha sido tachado, ese número es declarado primo, y se procede a tachar todos sus múltiplos. El proceso termina cuando el cuadrado del mayor número confirmado como primo es mayor que N....
Leer documento completo
Regístrate para leer el documento completo.