Volver atrás

Publicado por Eduardo González Vaquero | 30/07/2014

Estaba leyendo un libro de Isaac Asimov donde encontré una pequeña explicación de la criba de Eratóstenes, aunque no citaba el nombre de tal método. Navegando por internet, encontré por casualidad ese método en un foro (aquí enlace), y luego quise crear mi propio código (que se encontrará más abajo). La criba de Eratóstenes consiste en lo siguiente:

1. Empezamos desde el número 2 y pasamos de dos en dos por los demás números y los tachamos (resumidamente, tachamos 2x1,2x2,2x3...)
2. Buscamos el siguiente número que no esté tachado, que es el 3, y hacemos lo mismo pero de tres en tres.
3. Seguimos, y esta vez nos toca ir al 5; entonces, será lo mismo de antes pero de cinco en cinco.
4. Evidentemente, debemos tener un número como límite. Cuando lleguemos, todos los que no estén tachados son primos.

Aunque pueda parecer un método lento, es muy rápido si se ejecuta con una computadora. Hace tiempo busqué números por fuerza bruta, verificando uno a uno si es primo. Lo expongo a continuación:

#include <stdio.h>

int main() {
    int n,i,ok,p;
    printf("Introduce un número entero:");
    scanf("%d",&n);
    for(i = 1;i<=n;i++) {
        ok = 0;
        for(p = 2;p<i;p++) {
            if(i%p == 0) { ok = 1; break; }
        }
        if(ok != 1) printf("%d es número primo",i); 
    }
    system("PAUSE");
    return 0;
}

#include <stdio.h>
 
int main() {
    int i,n,prims[n],x=0,p,nums[n];
    n = 19000; // número hasta el que se quiere buscar
    for(i=2;i<=n;i++) {
        if(nums[i] != 1 || i == 2) {
            prims[x] = i;
            printf("El número %d es prim",i);
            for(p=2;(p*i)<=n;p++) {
                nums[(p*i)] = 1;
            }
            x++;
        }
    }
    printf("Hay %d números primos",x);
}

Siendo n el número final hasta el que buscar, prims[] el array donde se guardarán los números primos y x el número total de ellos.

Bibliografía:

· http://kekomundo.com/foro/index.php?topic=372297.0

· "Cien preguntas básicas sobre la ciencia" - Isaac Asimov

C/C++ cribanúmeros primosmatemáticasalgoritmosalgoritmia