eratosten*

/*
 * efficient up to 10e7 (struggles with 10e8, takes a few seconds to finish)
 * arb array has to be set to true (with memset or using "static" keyword)
 * n represents the upper limit in the range (0..n)
 * prime vector was made in global scope
*/

void eratosten(bool arb[], ll n){
    for(ll chk = 2; chk < n; chk++){
        if(!arb[chk]) continue;
            prime.push_back(chk);
            arb[chk] = true;

        for(ll i = chk * 2; i < n; i+=chk){
            if(arb[i]){
                if(i % chk != 0) arb[i] = true;
                else arb[i] = false;
            }
        }
    }
}