Сегментное сито Эратосфена?

Достаточно легко сделать простое решето:

for (int i=2; i<=N; i++){
    if (sieve[i]==0){
        cout << i << " is prime" << endl;
        for (int j = i; j<=N; j+=i){
            sieve[j]=1;
        }
    }
    cout << i << " has " << sieve[i] << " distinct prime factors\n";
}

Но что делать, если N очень велико и я не могу удержать это вид массива в памяти? Я просмотрел подходы к сегментированному решету, и они, похоже, включают поиск простых чисел до sqrt (N), но я не понимаю, как это работает. Что, если N очень велико (скажем, 10^18)?