|
<< Los números primos >> |
Lecciones anteriores:
Ninguna
Resumen:
Vamos a ver un par de formas de determinar si un número es primo o no. Además discutimos algunas propiedades de los primos.
Importancia de los primos:
Los números primos son aquellos que sólo se pueden dividir por 1 y por si mismos (el 1 no es primo). Ellos tienen un importante papel entre los enteros ya que :
Estos dos resultados son muy importantes, ¡y no son obvios!, aunque la demostración detallada es engorrosa, así que por ahora síganlos creyendo y usando cuando sea necesario.
Buscando Primos:
Una forma de ver si un número es primo es probar dividirlo por todos los números menores que él y si ninguno lo divide, ¡ganamos!, el número es primo. Este método se puede implementar en la siguiente función:
Defint A-Z 'Todas las variables son enteras Function EsPrimoLenta(N) Resultado = -1 For i = 2 To N-1 If N / i = Int ( N / i ) Then Resultado = 0 Exit For 'Sale del For...Next End If Next i EsPrimoLenta = Resultado End Function
La función devuelve un 0 si no es primo y un -1 si es primo. Ojo que anda mal si N=1.
Como indica el nombre, la función es un poco lenta, sobre todo cuando N es muy grande.
Pueden ver un ejemplo de como usar esta función en Testeador de primos.
La Raíz cuadrada:
Sin embargo, el divisor (distinto de n) más grande posible es n/2, así que podríamos probar sólo hasta n/2 en vez de n-1. Pero si n/2 es un número entero que es divisor de n, entonces 2 también es divisor (¡porque n dividido 2 es entero!), pero ya probamos antes si el 2 dividía a n. Así que no hace falta probar con el n/2. Entonces el siguiente divisor más grande posible es n/3, pero por un razonamiento análogo, tampoco hace falta probarlo ya que antes habíamos probado con 3.
¿Hasta cuando podemos
repetir esto? Bueno hasta que n/i = i, o sea hasta que
n = i2, o sea hasta que i=
n. Una
forma más formal de ver esto es que si d es un divisor de n,
entonces n/d es un divisor de n. Así que en vez de probar con
estos dos números hace falta probar sólo con el más chico.
Pero si uno es mayor que n entonces el otro es menor que n/n =n. Por
ello el más chico seguro que es menor que n y entonces sólo hace
falta probar hasta n.
Defint A-Z 'Todas las variables son enteras
Function EsPrimo( N )
Resultado = -1 'Si llega a ser primo devuelve -1
For i = 2 To Sqr( N )'Raiz cuadrada de n
If N / i = Int ( N / i ) Then
Resultado = 0 'No, no es primo y devuelve 0
Exit For 'Sale del For...Next
End If
Next i
EsPrimo = Resultado
End Function
Esta nueva forma es mucho más rápida que la anterior, y no por ello más difícil de escribir. Así que traten de usarla siempre. Otra mejora consiste en reemplazar la división con decimales por la división entera, que es mucho más rápida. En realidad usamos mod que nos da el resto de la división entera. En el programa hay que reemplazar la condición "N / i = Int ( N / i )" por "N Mod i = 0".
Otras Aplicaciones:
En general ver si un número grande (Muy Grande) es primo o no, es un problema difícil, aunque hay algoritmos bastante rápidos, pero basados en matemática más avanzada. Si tratamos de utilizar los métodos que vimos antes para ver si 10000000000000001 es primo, utilizando la criba nos quedamos sin memoria, y si tratamos de probar dividiendo por los anteriores es demasiado lento.
Sin embargo por más que sepamos que un número no es primo, factorizarlo en primos es muchísimo más difícil si el número es grande (digamos menos de 10 años). En esta dificultad se basa la seguridad de algunos sistemas de encriptación de clave pública por ejemplo el PGP, en este caso se tienen dos claves :
En realidad, la clave publica es el producto de dos primos grandes, y la privada son los dos primos.
Ejercicios:
Lecciones siguientes:
Divisor común mayor factorizando 
La idea es que hagan los ejercicios y piensen que otras cosas interesantes se pueden hacer relacionadas con estos temas. Cuéntennos lo que consiguieron y pregunten lo que no les salió. Envíen sus preguntas, dudas, sugerencias, experiencias y propuestas. Nuestra dirección es cym98@oma.org.ar .
También nos gustaría saber tu opinión sobre esta clase. Les pedimos que se tomen unos instantes y contesten estas preguntas. Con tu ayuda podremos hacer un curso cada vez mejor.
 OmaNet Curso CyM98 |
OmaNet - Educación Interactiva www.oma.org.ar/omanet | omanet@oma.org.ar |
| mensajes: webmaster@oma.org.ar |