OIA-Wiki

Este es un algoritmo para conocer todos los números primos hasta un número $n$. La idea consiste en ir recorriendo los números, y marcando los que no son primos. Cuando encontramos un número sin marcar, vamos a marcar a todos sus múltiplos (mayores a sí mismo) como que no son primos, ya que son múltiplos de este. Así por ejemplo tenemos:

Encontramos que el $2$ está sin marcar, entonces sabemos que es primo y marcamos a sus múltiplos:

Seguimos y encontramos que el $3$ está sin marcar, y marcamos a sus múltiplos ya que sabemos que no serán primos:

Y así seguimos, encontrando al $5$ y marcando sus múltiplos, al $7$...

criba.cpp

#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
    int N;
    cin>>N;
    vector<int> primes;
    vector<bool> criba(N+1, true); // empiezan todos como "true", posibles primos
    for(int i=2; i<=N; i++){
        if(criba[i]){
            primes.push_back(i);
            for(int j=i*2; j<=N; j+=i){
                criba[j]=false;
            }
        }
    }
}

Veamos que para cada número $i$, recorremos (o no) los múltiplos. Es decir, para el número $i$, hacemos $N/i$ iteraciones. Entonces la complejidad quedaría $N/2 + N/3 + N/4 + \ldots N/(N-1) + 1 = N*(1/2 + 1/3 + \ldots) = N*log(N)$. Aunque en realidad, para los números compuestos no entramos al $if$. La complejidad de esta criba (haciendo las cuentas más detalladamente) es $O(N*log(log(N)))$, que es muy cercano a ser lineal, es decir, si $N=10^7$, $log(N)=24$ y $log(log(N))=log(24)=5$.

, j=i*i, ir hasta la raiz y despues nos quedan los primos (O(N))