Tag: 引发

Eratosthenes的分割筛？

做一个简单的筛子很容易： 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很大，我不能在内存中保存这样的数组呢？ 我已经查找了分段的sieve方法，它们似乎涉及到sqrt（N）findprimes，但我不明白它是如何工作的。 如果N很大（比如10 ^ 18）呢？