Criba De Eratosten

-------------------------------------------------
Criba de Eratóstenes

La criba de Eratóstenes es un algoritmo que permite hallar todos los números primos menores que un 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 número entero que no ha sidotachado, 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.
-------------------------------------------------
Pseudocódigo
Algoritmo Criba de Eratóstenes (Complejidad ) |
Entrada: Un número natural Salida: El conjunto de números primos anteriores a  (incluyendo ) 1. Escribatodos los números naturales desde  hasta  2. Para  desde  hasta  haga lo siguiente: 1. Si  no ha sido marcado entonces: de dos en dos así sucesivamente 1. Para  desde  hasta  haga lo siguiente: 1. Ponga una marca en  3. El resultado es: Todos los números sin marca |
Acerca de la notación:
*  es la función parte entera de 
*  es el cociente de dividir  entre 
Parasu implementación en una computadora, normalmente se maneja un vector de tipo lógico con  elementos. De esta manera, la posición  contiene el valor Verdadero como representación de que  ha sido marcado y Falso en otro caso.

-------------------------------------------------
Refinamiento
Una implementación más eficiente requiere crear un arreglo con solo los impares (pues los pares distintosde 2 ya se sabe que no son primos). En este caso se deben tachar los múltiplos impares de 3,4,5,7
Los múltiplos impares del primo  son . Debemos tachar desde  en adelante pues siempre se empieza a tachar desde . Note que si  entonces el primer múltiplo de  es .
Si corresponde tachar los múltiplos del primo ésimo , se inicia en  pues antes de , ya se han tachado  (los pares),  (los múltiplos de3), ,...,.
Así, si  ya no habría algo que tachar, por eso terminamos ahí el programa.
En la implementación se usa un arreglo "esPrimo()" tipo boolean. Aquí, "esPrimo(i)" representa al número impar .
Note que si  entonces  está representado por "esPrimo((p-3)/2)".
Así, si se sabe que  es primo, sus múltiplos (impares) no son primos, es decir, debemos poner
"esPrimo(((2k+1)p-3)/2)=false,k=i+1,i+2,..."
En la implementación iniciamos con el arreglo "esPrimo()" con todas sus entradas true. Iniciando en , ponemos "esPrimo(((2k+1)3-3)/2)=false, k=0+1,0+2,..." y así sucesivamente: para cada nuevo  primero preguntamos si "esPrimo(i)=true", si es así, "tachamos" sus múltiplos poniendo la respectiva entrada "false".
La siguiente función, en VBA, es una función que recibe  y devuelve un arreglocon los primos  (ver más detalles en la segunda referencia)
Números coprinos
-------------------------------------------------
Definición
Dos números enteros son coprimos o primos entre sí si su máximo común divisor (mcd) es 1. En tal caso los únicos divisores comunes son -1 y 1.
Esto equivale a decir que la fracción  es irreductible (no se puede simplificar).-------------------------------------------------
Ejemplos
* 5 y 7 son coprimos porque son ambos primos (y distintos, desde luego).
* 11 y 49 son coprimos porque 11 es primo y 49 no es múltiple de 11.
* 36 y 91 son coprimos porque en la descomposición en factores primos de cada uno, no aparece ningún factor común: 36 = 22×32 y 91 = 7×13.
* 234 y 658 no son coprimos porque son ambos pares, y por lo tanto 2 es undivisor común mayor que 1.
Casos muy particulares:
* -1 y 1 son primos con todos los enteros.
* 0 es primo sólo con -1 y 1.
* n y n + 1 siempre son coprimos.
-------------------------------------------------
Propiedades elementales
Si a y b son coprimos entonces su mínimo común múltiplo (mcm) es el producto a·b, que es también el menor denominador común de las fracciones...