Uno de los más rápidos... usa el teorema de abajo.
Teorema:
Para todo número primo p > 3, se tiene que p=6k+1 ó p=6k-1
Demostración:
Todos los entero pueden expresarse exactamente de un de las 6 posibles formas:
6k, 6k+1, 6k+2, 6k+3, 6k-2, ó 6k-1
6k es divisible por 6, por lo que no es primo
6k+2 es par, por lo que no es primo
6k+3=3(2k+1) es divisible por 3, por lo que no es primo
6k-2 es par por lo que no es primo
Por tanto, los números primos tienen que expresarse de la forma 6k+1 ó 6k-1.
Note que no todos los números de esa forma son necesariamente primos.
Algoritmo para determinar si un número es primo
En muchas aplicaciones es necesario conocer si un número n es o no primo. Cuando n es muy grande, los algoritmos conocidos son muy ineficientes. Veamos el siguente que es bastante rápido para n no muy grandes.
Determinaremos si un número n es primo, si algún divisor no trivial de n es encontrado, puede asegurarse de que n es compuesto, si ningún divisor es encontrado entonces concluimos que n es primo. El algoritmo está basado entonces en una búsqueda exaustiva de un divisor de n. A continuación un pseudocódigo del algoritmo.
PRIME (x) // x > 3
1 if x mod 6 <> 1 and x mod 6 <> 5
2 then return FALSE
3 r = SQRT(x)
4 i = 1
5 while 6*i-1 <= r do
6 if x mod (6*i-1) = 0
7 then return FALSE
8 if x mod (6*i+1) = 0
9 then return FALSE
10 i = i + 1
11 return TRUE
La criba de Erastótenes
Este un algoritmo conocido desde la antigüedad, para determinar todos los números primos desde 2 hasta un cierto valor n.
El algoritmo está basado en "marcar" todos los números que son múltiplos de algún otro menor. Al final, los números que "hayan sobrevivido a tal marcado" por supuesto, son primos.
CRIBA_DE_ERASTOTENES (max)
1 for i = 2 to max do
2 marked[i] = FALSE
3 for i = 2 to max do
4 if marked[i] = FALSE
5 then k = 2*i
6 while k <= max do
7 marked[k] = TRUE
8 k = k + i
9 return marked
Algoritmos
Nociones elementales en la teoría de los números
Tema por:
Ronny López Trujillo
Selección Nacional de Cuba
XIV IOI Yong-In Korea 2002
Visita la siguinete dirección: http://www.lawebdelprogramador.com/codigo/enlace.php?idp=1319&id=69&texto=Pascal/Turbo+Pascal
