Sacando números primos por la Criba de Eratóstenes en C - Brainum

Sacando números primos por la Criba de Eratóstenes en C

Volver atrás

Publicado por |

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;
}

Buscar números primos mediante la criba de Eratóstenes:

#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

Programación

Redes sociales

Twitter BrainumGoogle Plus BrainumFacebook Brainum


Política de privacidad