Programa - C++: Detector de números primos

Detector de números primos

Hola de nuevo a otra entrada de Code0x66 ;D
¿Quién ha querido alguna vez una base de datos con muchos primos, eh? Pues algo así hará el programa que traigo hoy aquí.

Este programa, va a hacer 3 cosas:

1. Va a ir escribiendo en orden todos los primos que vaya detectando, en un archivo
2. Al reabrir el programa, retomará el último primo conseguido en la última sesión
3. Como curiosidad, calculará el tiempo en detectar los primos

Lo primero, necesitamos una función que nos diga si un número es primo, o no.
"Un número es primo si sólo es divisible entre 1 y entre sí mismo, y que sea mayor que 1"
Por ejemplo, 2, 3 y 11 son números primos.
¿Cómo sabremos si lo son? Pues calcularemos si es divisible entre los números entre 1 y él mismo. Si es divisible entre alguno, significa que ya no es primo. (Divisible significa que el resto (%) entre el divisor y el dividendo sea 0.)
Pues allá vamos, con un bucle muy sencillo:

bool primo(uint64_t n){
    if(n%2==0) return false;
    uint64_t i=3;
    for (;n%i!=0; i+=2){
        if(i>=n/2){
            i=n;
            break;
        }
    }
    return i==n;
}

En primer lugar: usamos uint64_t porque es unsigned (los primos no serán negativos), y 64 para asegurarnos de poder trabajar con números grandes.
Ese for trabaja mientras el resto entre el número y el índice (que va desde 3 hasta el número) sea 0.
Cuando el bucle se rompa, significará 1 de 2: o que i == n (es primo), o que encontró un divisor por el medio (no es primo).
¿Esta función entendida? Para darle velocidad, he puesto i+=2, porque si no es divisible entre 2, tampoco lo será entre un número par. Como esta, se le pueden hacer otras mejoras al código. Eso ya es trabajo vuestro ;D

Y ahora vamos con el código principal.
¿Qué hará? Pues...

1. Pedirá al usuario el número de primos a calcular
2. Leerá el último primo de la lista, para ponerse al día
3. Calculará N primos

A ello. Las librerías que usaremos serán iostream, fstream, y ctime para medir tiempos. Recordad poner using namespace std;, o colocar std:: delante de las clases y funciones.

Y como me gusta presentar primero el código, pues vamos a ello:

int main () {
    while(true){
        uint64_t u=2, g=0, h=0;
        cout << "Numero de primos a conseguir: ";
        cin >> g;
        /*************************************/
        ifstream leer("primos.txt", ios::ate);
        char n=0;
        if(leer){
            while(n!='\n'){
                leer.unget();
                n = leer.get();
                leer.unget();
            }
            leer.get();
            leer >> u;
        }
        leer.close();
        /*************************************/
        ofstream escribir("primos.txt", ios::app);
        if(u==2){
            escribir << u--;
        }
        
        clock_t timer = clock();
        while(h<g){
            u+=2;
            if(primo(u)){
                escribir << endl << u;
                ++h;
            }
        }
        cout << endl << "Conseguidos " << h << " primos en " << ((clock()-timer)*1000)/CLOCKS_PER_SEC << " milisegundos." << endl << endl;
    }
}

*Las 3 partes del código que enumeré antes, están partidas por los separadores "/**/"*

La primera parte, pedir el número de primos a conseguir, no tiene ningún misterio.

La segunda, ya tiene más concepto. Hicimos el ifstream con ios::ate, (at-the-end). El stream del archivo empieza en su final. Como el archivo coloca cada número separado de un '\n', vamos haciendo leer.unget() para retroceder en el stream, y en definitiva, retrodecemos hasta el próximo '\n'. A partir de ahí, leemos el número.

Y ahora el código "importante". Tercera parte. Comenzamos a escribir. El ofstream lo hemos abierto con ios::app, (append). Empezará a escribir en el final.
Importante: la variable 'u' guarda el número actual. 'g' guarda el número de primos a conseguir. 'h' guarda el número de primos conseguidos.
Si u==2, es decir, si no se ha leído ningún primo del archivo, escribimos el 2, y disminuímos 'u' en 1. Recordar que poner "u--"(post-decremento), decrementa la variable después de la sentencia.
¿Por qué hacemos eso? 2 es un caso especial. Es el único primo que es par. Así que, como luego tendremos un "u+=2", acabará siendo 3, que es nuestro próximo objetivo.

Ahora va un "clock_t", que es una variable con la que guardaremos el tiempo actual. Y luego, solo queda, mientras el número de primos obtenidos (h) sea menor que el requerido (g), los calculamos. Llamamos a nuestra función primo(), y si retorna true, escribimos el número en el archivo.

Entiendo que pueda ser algo confuso el código, pero si os fijáis un rato, seguro que lo entendéis.

Y hasta ahí es todo. Esto fué un rescate de un código antiguo que tenía. Cabe decir, que al andar por números grandes, empezará a ir cada vez más lento el programa. Así que cuidado con cuantos números le pedíis que calcule. Yo recomiendo como máximo pedirle algo así como 50.000, cosa que me tardó en un momento dado unos 3 minutos a mi :(

Pues venga, a disfrutar del código, y de C++ también.
Ciao!