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）呢？
分段筛的基本思想是select小于n的平方根的筛选素数，select一个合理的大段尺寸，然后适合记忆，然后从最小的开始依次筛选每个段。 在第一段中，计算段内每个筛分素数的最小倍数，然后筛选素数的倍数以正常方式标记为合成; 当所有筛分质数都被使用时，其余未标记的数字是质数。 然后，对于下一个细分市场，对于每个筛选的黄金，您已经知道当前细分市场的第一个倍数（这是筛选结束前一个细分市场的倍数），所以您筛选每个筛选的黄金，等等直到你完成。
n的大小并不重要，除了较大的n将比较小的n需要更长的筛选时间。 重要的大小就是段的大小，它应该尽可能大（比如机器上主要的内存caching的大小）。
你可以在这里看到一个简单的分段筛的实现。 请注意，分段筛将比另一个答案中提到的奥尼尔的优先级队列筛要快得多。 如果你有兴趣，这里有一个实现。
编辑：我写了这个不同的目的，但我会在这里显示，因为它可能是有用的：
虽然Eratosthenes的筛子非常快，但它需要O（n）空间。 对于筛选素数可以减less到O（sqrt（n）），通过在连续的片段中进行筛分，将O（1）减less到比特数。 在第一个分段中，计算分段内每个筛分素数的最小倍数，然后以正常方式将筛选素数的倍数标记为合成; 当所有筛分质数都被使用时，其余未标记的数字是质数。 然后，对于下一个分段，每个筛分素数的最小倍数是在前一个分段中结束筛分的倍数，因此筛分继续直到完成。
考虑筛选范围从100到200的20个片段。五个筛选素数是3,5,7,11和13.在从100到120的第一个片段中，位arrays具有十个插槽，插槽0对应于101 ，时隙k对应于100 + 2k + 1，时隙9对应于119.分段中3的最小倍数是105，对应于时隙2; 时隙2 + 3 = 5和5 + 3 = 8也是3的倍数。时隙2的5的最小倍数是105，时隙2 + 5 = 7也是5的倍数.7的最小倍数是105在时隙2处，时隙2 + 7 = 9也是7的倍数。依此类推。
函数primesRange需要参数lo，hi和delta; lo和hi必须是偶数，lo <hi，lo必须大于sqrt（hi）。 段的大小是两倍三angular洲。 Ps是一个包含小于sqrt（hi）的筛选素数的链表，删除了2，因为偶数被忽略。 Q是一个链表，其中包含在相应筛选素数的当前段中最小倍数的筛子位arrays中的触发。 在每个分段之后，lo前进两倍delta，所以对应于筛分比特列的索引i的数目是lo + 2i + 1。
function primesRange(lo, hi, delta) function qInit(p) return (-1/2 * (lo + p + 1)) % p function qReset(p, q) return (q - delta) % p sieve := makeArray(0..delta-1) ps := tail(primes(sqrt(hi))) qs := map(qInit, ps) while lo < hi for i from 0 to delta-1 sieve[i] := True for p,q in ps,qs for i from q to delta step p sieve[i] := False qs := map(qReset, ps, qs) for i,t from 0,lo+1 to delta-1,hi step 1,2 if sieve[i] output t lo := lo + 2 * delta
当被称为素数范围（100,200,10）时，筛选素数ps是[3,5,7,11,13]。 qs最初是对应于最小倍数105,105,105,121和117的[2,2,2,10,8]，并且针对第二段被重置为对应于最小倍数的[1,2,6,0,11]倍数123,125,133,121和143。
您可以在http://ideone.com/iHYr1f上看到这个程序正在运行。; 除了上面显示的链接之外，如果您对使用素数进行编程感兴趣，我会在我的博客上谦虚地推荐这篇文章 。
有一个基于优先级队列的Sieve版本可以产生尽可能多的素数，而不是全部达到上限。 在经典论文“Eratosthenes的真正筛”中讨论了这个问题，并且使用了“eratosthenes优先队列筛选”的search引擎，在不同的编程语言中出现了不less实现。
只是我们正在用我们的筛子来分割。 基本的想法是假设我们必须找出85和100之间的素数。我们必须使用传统的筛子，但是按照下面描述的方式：
所以我们取第一个素数2，将起始数除以2（85/2），取小数得到p = 42，再乘以2得到p = 84，从这里开始加2直到最后一个数字为止。所以我们所做的是我们已经去除了范围内所有2个因素（86,88,90,92,94,96,98,100）。
我们取下一个素数3，将起始数除以3（85/3），取小数得到p = 28，再乘以3，得到p = 84，从这里开始加3最后一个数字。所以我们所做的是我们已经去除了范围内的所有3个因素（87,90,93,96,99）。
取下一个素数= 5等………………继续做上述步骤。你可以得到素数（2,3,5,7， …）使用传统的筛子sqrt（n），然后将其用于分段筛。
基于Swapnil Kumar答案，我用C做了以下algorithm。它是用mingw32-make.exe构build的。
#include<math.h> #include<stdio.h> #include<stdlib.h> int main() { const int MAX_PRIME_NUMBERS = 5000000;//The number of prime numbers we are looking for long long *prime_numbers = malloc(sizeof(long long) * MAX_PRIME_NUMBERS); prime_numbers[0] = 2; prime_numbers[1] = 3; prime_numbers[2] = 5; prime_numbers[3] = 7; prime_numbers[4] = 11; prime_numbers[5] = 13; prime_numbers[6] = 17; prime_numbers[7] = 19; prime_numbers[8] = 23; prime_numbers[9] = 29; const int BUFFER_POSSIBLE_PRIMES = 29 * 29;//Because the greatest prime number we have is 29 in the 10th position so I started with a block of 841 numbers int qt_calculated_primes = 10;//10 because we initialized the array with the ten first primes int possible_primes[BUFFER_POSSIBLE_PRIMES];//Will store the booleans to check valid primes long long iteration = 0;//Used as multiplier to the range of the buffer possible_primes int i;//Simple counter for loops while(qt_calculated_primes < MAX_PRIME_NUMBERS) { for (i = 0; i < BUFFER_POSSIBLE_PRIMES; i++) possible_primes[i] = 1;//set the number as prime int biggest_possible_prime = sqrt((iteration + 1) * BUFFER_POSSIBLE_PRIMES); int k = 0; long long prime = prime_numbers[k];//First prime to be used in the check while (prime <= biggest_possible_prime)//We don't need to check primes bigger than the square root { for (i = 0; i < BUFFER_POSSIBLE_PRIMES; i++) if ((iteration * BUFFER_POSSIBLE_PRIMES + i) % prime == 0) possible_primes[i] = 0; if (++k == qt_calculated_primes) break; prime = prime_numbers[k]; } for (i = 0; i < BUFFER_POSSIBLE_PRIMES; i++) if (possible_primes[i]) { if ((qt_calculated_primes < MAX_PRIME_NUMBERS) && ((iteration * BUFFER_POSSIBLE_PRIMES + i) != 1)) { prime_numbers[qt_calculated_primes] = iteration * BUFFER_POSSIBLE_PRIMES + i; printf("%d\n", prime_numbers[qt_calculated_primes]); qt_calculated_primes++; } else if (!(qt_calculated_primes < MAX_PRIME_NUMBERS)) break; } iteration++; } return 0; }
它设置了要find的素数的最大值，然后用已知的素数如2,3,5 … 29初始化一个数组。 所以我们做一个缓冲区来存储可能素数的分片，这个缓冲区不能大于最大的初始素数，在这种情况下是29。
我确信有很多优化可以用来提高性能，比如并行分段分析过程和跳过2,3和5倍数，但是作为低内存消耗的一个例子。
如果有人希望看到C ++的实现，这里是我的：
void sito_delta( int delta, std::vector<int> &res) { std::unique_ptr<int[]> results(new int[delta+1]); for(int i = 0; i <= delta; ++i) results[i] = 1; int pierw = sqrt(delta); for (int j = 2; j <= pierw; ++j) { if(results[j]) { for (int k = 2*j; k <= delta; k+=j) { results[k]=0; } } } for (int m = 2; m <= delta; ++m) if (results[m]) { res.push_back(m); std::cout<<","<<m; } }; void sito_segment(int n,std::vector<int> &fiPri) { int delta = sqrt(n); if (delta>10) { sito_segment(delta,fiPri); // COmpute using fiPri as primes // n=n,prime = fiPri; std::vector<int> prime=fiPri; int offset = delta; int low = offset; int high = offset * 2; while (low < n) { if (high >=n ) high = n; int mark[offset+1]; for (int s=0;s<=offset;++s) mark[s]=1; for(int j = 0; j< prime.size(); ++j) { int lowMinimum = (low/prime[j]) * prime[j]; if(lowMinimum < low) lowMinimum += prime[j]; for(int k = lowMinimum; k<=high;k+=prime[j]) mark[k-low]=0; } for(int i = low; i <= high; i++) if(mark[i-low]) { fiPri.push_back(i); std::cout<<","<<i; } low=low+offset; high=high+offset; } } else { std::vector<int> prime; sito_delta(delta, prime); // fiPri = prime; // int offset = delta; int low = offset; int high = offset * 2; // Process segments one by one while (low < n) { if (high >= n) high = n; int mark[offset+1]; for (int s = 0; s <= offset; ++s) mark[s] = 1; for (int j = 0; j < prime.size(); ++j) { // find the minimum number in [low..high] that is // multiple of prime[i] (divisible by prime[j]) int lowMinimum = (low/prime[j]) * prime[j]; if(lowMinimum < low) lowMinimum += prime[j]; //Mark multiples of prime[i] in [low..high] for (int k = lowMinimum; k <= high; k+=prime[j]) mark[k-low] = 0; } for (int i = low; i <= high; i++) if(mark[i-low]) { fiPri.push_back(i); std::cout<<","<<i; } low = low + offset; high = high + offset; } } }; int main() { std::vector<int> fiPri; sito_segment(1013,fiPri); }
