Dificultad:

Se necesitan conocimientos elementales de matemática. Puede ser útil ver las lecciones anteriores para repasar algunos de los conocimientos de computación necesarios.

Lecciones anteriores:

Los números primos

Resumen:

Vamos a ver un método propuesto por Eratóstenes para obtener la lista de todos los primos menores, hasta cierto valor. El método es un poco más rápido que ver uno por uno si los números son primos. La desventaja es que se necesita más memoria para guardar los resultados intermedios.

Criba de Eratóstenes:

Los pasos del método son:

• Primero hacemos una lista de todos los números desde 2 hasta n.
• Tomamos el 2 y tachamos todos los múltiplos de 2 en la lista.
• Buscamos el primer número sin tachar y tachamos todos sus múltiplos mayores.
• Repetimos el paso anterior hasta que se acaben los números.
• Los que quedaron sin tachar son los que no tienen divisores (propios) o sea los primos.

Veamos algunos pasos a mano

• Primero hacemos una lista de todos los números desde 2 hasta n.

    1  2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29

• Tomamos el 2 y tachamos todos los múltiplos de 2 en la lista.

    1  2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29

• Repetimos: Buscamos el primer número sin tachar y tachamos todos sus múltiplos mayores. (El 3)

    1  2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29

• Repetimos: Buscamos el primer número sin tachar y tachamos todos sus múltiplos mayores. (El 5)

    1  2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29

• Los que quedaron sin tachar son los que no tienen divisores (propios) o sea los primos.

    1  2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29

El programa (version dibujada):

Vamos a simular la lista de números como un vector, con n casilleros.

• Si en el casillero hay un -1 el número esta sin tachar.
• Si en el casillero hay un 0 entonces el número esta tachado

Para que sea más facil de ver, vamos a ir mostrando en la pantalla como vamos tachando los números. Así que el programa utiliza algunas instrucciones como Locate y Color para lograr efectos visuales en la pantalla. Al ejecutarlo hay que tocar Enter, para que el programa siga avanzando.

Inicialmente todos los números son de color gris clarito, porque todavia no sabemos si son primos o no.Cada vez que encontramos un primo, lo marcamos en celeste y a todos sus múltiplos en azul. Después cambiamos los colores a blanco y gris oscuro respectivamente. De esta manera podemos distinguir los números recien marcados de todos los que ya habíamos marcado. Al final nos quedan todos los primos de color blanco, y los compuestos de color gris oscuro.

Defint A-Z
Ancho = 4
'Numero de NumCol (<=20)
NumCol = 10
'Numero de NumFil (<=24)
NumFil = 20
'n= Numero mas grande
n = NumFil * NumCol - 1

'Colores
Celeste = 9
Azul = 1
Blanco = 15
Claro = 7
Oscuro = 8

Cls
'Armamos la "lista"
Dim lista(1 To n)
For i = 1 To n
  lista(i) = -1
  Locate i \ NumCol + 1, (i Mod NumCol) * Ancho + 1
  Color Claro
  Print i
Next i
lista(1) = 0'1 no es primo
Locate 1 \ NumCol + 1, (1 Mod NumCol) * Ancho + 1
Color Oscuro
Print 1
Sleep

'y ahora empezamos a tachar
For p = 1 To n
  If lista(p) = -1 Then
    'p no esta tachado, asi que es primo
    
    'Primera Pasada: Los marcamos de un color
    Locate p \ NumCol + 1, (p Mod NumCol) * Ancho + 1
    Color Celeste
    Print p
    For j = 2 * p To n Step p
      lista(j) = 0
      Locate j \ NumCol + 1, (j Mod NumCol) * Ancho + 1
      Color Azul
      Print j
    Next j
    Sleep
        
    'Segunda Pasada: Los marcamos de otro colos
    Locate p \ NumCol + 1, (p Mod NumCol) * Ancho + 1
    Color Blanco
    Print p
    For j = 2 * p To n Step p
      lista(j) = 0
      Locate j \ NumCol + 1, (j Mod NumCol) * Ancho + 1
      Color Oscuro
      Print j
    Next j
    Sleep
        
  End If
Next p

Ahora vamos a sacar casi todo lo que muestra mensajes en pantalla, de manera que el programa quede más rápido. Por otro lado vamos a agregar algunos truquitos adicionales para ganar velocidad.

Para cada primo p, el múltiplo (propio) más chico que no esta tachado es p². Así que los primos menores que la raíz cuadrada de n pueden tener múltiplos sin tachar en la tabla, pero los mayores no. Así que los analizamos por separado para ganar algo de velocidad.

Defint A-Z 
'Buscamos los primos hasta el 999
n = 999 

'Armamos la "lista"
Dim Lista (1 To n)
For i = 1 To n
     lista(i) = -1 
Next i
Lista(1)=0  '1 no es primo

'Busco los primos chicos
For p = 2 To Int(Sqr(n)) 
     If lista(p) = -1 Then
          'p no esta tachado, asi que es primo
          Print i
          For j = p*p To n Step p 
              lista(j) = 0
          Next j
     End If
Next p

'Busco los primos grandes
For p = Int(Sqr(n))+1 To n
     If lista(p) = -1 Then
          'p no esta tachado, asi que es primo
          Print p
     End If
Next p

Otras formas de utilizarlo:

En general, este métod es útil para programas en los que se generan muchos números y hay que ver si alguno de ellos es primo, por ejemplo

Consideramos todos los numeros de la forma a³+b³+c³ con a, b y c enteros positivos. Buscar los que son primos y menores que 1000000.

Lo más sencillo es hacer tres ciclos For...Next (para a, b y c) entre 1 y 99, y ver si los números son suficientemente chicos y primos. Para ver si son primos, se puede utilizar una funcion como la que vimos en la lección anterior. Pero cada vez que salga el 817 vamos a tener que ver si realmente es primo o no y eso es bastante lento.

Podemos hacer una funcion parecida a las anteriores. El ejemplo que mostramos no hace nada interesante, solo repite el valor 0 o -1 según este en la lista. En general seria bueno agregarle que se fije si el primo está en el rango adecuado. (Si es más grande, una posibilidad es hacer que vea si es primo o no por el método tradicional. Y si es chico se fija en la tabla y listo.)

Defint A-Z 'Todas las variables son enteras
Function EsPrimoCriba(N)
     EsPrimoCriba = lista(N)
End Function

Ejercicios:

1. Modificar el programa para usar la operación mod. Comparar el tiempo de ejecución con el que usa la división con decimales.
   
   
2. Utilizando la función EsPrimo de la lección anterior, escribir un programa que imprima la lista de los primos menores que 10000. Comparar el tiempo de ejecución de este programa con la criba.
   
   
3. Combinar la criba con la funcion EsPrimo, de manera de probar sólo con los primos. ¿Anda más rápido o más lento?
   
   
4. Contar cuantos primos hay menores que 10, 100, 1000, 10000, 100000 ( y si pueden más). Buscar alguna relación (ojo: muuuy difícil).
   

Lecciones siguientes:

Factorizando al azar