La forma mas fácil de saber si un número es primo o no
Escrita en: Jul 13, 2007 // Matemáticas.The Prime Game es un juego tan misterioso de los números primos como lo es la espiral de ulam .
Pídele a un amigo que escriba un número primo. Apuesta a que puedes tachar cero o más dígitos para dejarlo en uno de los siguientes 26 números primos:
2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, 66600049.
Por ejemplo si tu amigo escribe 43, puedes tachar el 4 para llegar al 3. Si escribe 946969 puedes tachar el primer 9 y los dos 6 para obtener 499.
Esto lo vi en microsiervos , y como cuentas ellos este es un método para saber rápidamente si un número es primo o no. ¡Vaya …..!, de haber sabido esto, mi maestra de Estructura de Datos me hubiera tratado de genio cuando me pidió el algoritmo para buscar si un número era primo o no en su examen.
Según recuerdo hay una historia famosa de Euler, donde demuestra que un número muy grande no es primo, recordemos que en aquella época era difícil saberlo. Supongo que si Euler viviera, se moriría del coraje al pensar cualquier niño lo puede saber.
La demostración formal esta aquí , por lo que sabemos que se cumple en todos los casos. Me pregunto entonces por que tanto alboroto de algunos matemáticos para saber si un número es primo o no.
4
Jul 13, 2007, 3:01 amEl teorema dice, si p es primo, entonces se puede hacer ese algoritmo, pero el contrario no es cierto, es decir, si a algun numero le aplico el algoritmo, no implica que ese numero sea primo. Por ejemplo, es obvio que el 36 no es primo, sin embargo, tachando un 6 nos queda el 3, que se encuentra en la familia. En realidad, el teorema nos separa los naturales en dos conjuntos, los que no se pueden reducir a alguno de la lista (que podemos asegurar que no son primos) y los que si se pueden reducir a alguno de la lista (que no se tiene idea si es primo o no). Desde mi punto de vista, este teorema es muy débil para distinguir entre si un número es primo o no. Aunque existe un teorema de teoría de números que incluye necesidad y suficiencia. Si te interesa, puedes buscarlo como “Teorema de Wilson”, cuya demostración es masomenos sencilla. Lo malo de este teorema es que es pobre computacionalmente hablando.
Michoacano
Jul 13, 2007, 3:39 amEs cierto gracias 4 :S