Criba lineal (criba de Euler) con complejidad O(n)

La idea central de este algoritmo es que cada número compuesto se marca usando su menor factor primo. Para un número compuesto \(u = i \times p\), donde \(p\) es su menor factor primo, \(u\) se marca en el momento en que se procesa \(i \times p\). Como \(i\) es menor que \(u\), se garantiza que \(u\) se marcará antes de ser procesaod.

En el código, la condición if ((i % primos[j]) == 0) break; evita marcas redundantes. Si \(i\) es divisible por un primo \(p_j\), entonces \(i = p_j \times x\). Al intentar marcar el siguiente número \(i \times p_{j+1}\), equivaldría a \(p_j \times x \times p_{j+1}\). Dado que los primos se almacenan en orden ascendente, \(p_j < p_{j+1}\), usar \(p_j\) como manor factor es más eficiente. El break asegura que no se continúe con primos mayores, ya que \(p_j\) ya cubre el caso.

Además, al marcar números compuestos, se cumple que \(p \leq i\), porque \(p\) se deriva de los factores primos ya conocidos de \(i\). El bucle que marca los compuestos no necesita verificar que \(j\) no exceda el conteo de primos, ya que el break se activa antes, asegurando que solo se usen los factores primos relevantes.

#include <iostream>
#include <vector>

using namespace std;

const int LIMITE = 1000010;
vector<int> numerosPrimos;
bool marcado[LIMITE];

void cribaLineal(int limite) {
    for (int num = 2; num <= limite; ++num) {
        if (!marcado[num]) {
            numerosPrimos.push_back(num);
        }
        for (size_t idx = 0; idx < numerosPrimos.size(); ++idx) {
            int primo = numerosPrimos[idx];
            if (primo * num > limite) break;
            marcado[primo * num] = true;
            if (num % primo == 0) break;
        }
    }
}

int main() {
    int n;
    cin >> n;
    cribaLineal(n);
    cout << numerosPrimos.size() << endl;
    return 0;
}

Un punto crítico es el manejo del límite \(n\). Si se usa num < n en lugar de num <= n, el efecto es similar a reducir \(n\) en uno. Esto podría dejar de marcar algunos números compuestos, llevando a resultados incorrectos. Es esencial mantener condiciones de límite consistentes para evitar errores sutiles.

Criba de Eratóstenes con complejidad O(n log log n)

Este algoritmo se basa en iterar sobre los números y, para cada primo encontrado, marcar sus múltiplos. Una desventaja es que un número compuesto puede ser marcado varias veces si tiene múltiples factores primos, lo que reduce la eficiencia en copmaración con la criba lineal.

#include <iostream>
#include <vector>

using namespace std;

const int MAXIMO = 1000010;
vector<int> primosEncontrados;
bool esCompuesto[MAXIMO];

void cribaEratostenes(int limite) {
    for (int candidato = 2; candidato <= limite; ++candidato) {
        if (!esCompuesto[candidato]) {
            primosEncontrados.push_back(candidato);
            for (int multiplo = candidato * 2; multiplo <= limite; multiplo += candidato) {
                esCompuesto[multiplo] = true;
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    cribaEratostenes(n);
    cout << primosEncontrados.size() << endl;
    return 0;
}

En ambas implementaciones, se utiliza un arreglo booleano para marcar los números compuestos y un vector para almacenar los primos. La elección entre estos algoritmos depende de los requisitos de eficiencia: la criba lineal es óptima para grandes rangos, mientras que la de Eratóstenes es más simple de implementar.