Computación ET-344

Encontrar todos los números primos, de manera eficiente, menores a un límite dado.

/*Copyright 2021 Germán Andrés Xander <german.xander@fio.unam.edu.ar>
*
* Encontrar todos los números primos, de manera eficiente, menores a un límte dado.
* Para ello se utiliza el método de Criba de Eratóstenes
* https://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes
*/

#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;

void criba(int valor){
    bool marcados[valor]={}; //se crea un arreglo de tamaño ingresado
    //¡¡¡CUIDADO!!! analizar el problema con esto
    
    // se recorre y marca como true los valores que son múltiplos
    for (int p=2; p*p<valor; p++){ //p*p es mucho más "barato" que raíz de
        // si p no está marcado es un primo
        if (marcados[p] == false){
            // marcar todos los múltiplus de p
            //se comienza de p*p porque es el 1er múltiplo de p que no es múltiplo de un número menor que p
            for (int i=p*p; i<valor; i+=p){
                marcados[i] = true;
            }
        }
    }
    // mostrar todos los primos
    for (int p=2; p<valor; p++){
        marcados[p] ? cout:(cout << p<<" ")
    }
}

int main(int argc, char **argv){
    auto start = high_resolution_clock::now();
    
    criba(10000); //¡¡¡CUIDADO!!!
    
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cout <<endl<< "duracion "<< duration.count() << " us"<<endl;
    return 0;
}