相关疑难解决方法(0)

制作一个简单的筛子很容易:

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)怎么办？