算法设计（分段筛(Segmented Sieve)介绍和代码实现） _分段筛

本文概述

C
C ++
Java
Python3
C#

给定数字n, 请打印所有小于n的素数。例如, 如果给定数字为10, 则输出2、3、5、7。
天真的方法是从0到n-1循环运行, 并检查每个数字的素数。使用更好的方法：简单的Eratosthenes Sieve.
C

//This functions finds all primes smaller than 'limit' //using simple sieve of eratosthenes. void simpleSieve( int limit) { //Create a boolean array "mark[0..limit-1]" and //initialize all entries of it as true. A value //in mark will finally be false if 'p' is Not //a prime, else true. bool mark[limit]; memset (mark, true , sizeof (mark)); //One by one traverse all numbers so that their //multiples can be marked as composite. for ( int p=2; p*p< limit; p++) { //If p is not changed, then it is a prime if (mark == true ) { //Update all multiples of p for ( int i=p*p; i< limit; i+=p) mark[i] = false ; } }//Print all prime numbers and store them in prime for ( int p=2; p< limit; p++) if (mark == true ) cout < < p < < "" ; }

简单筛的问题：
Eratosthenes的筛子看起来不错, 但是考虑n较大的情况, 简单筛子会遇到以下问题。

大小为Θ(n)的数组可能不适合内存
简单的Sieve甚至对于稍大的n也不友好。该算法遍历数组时没有参考位置

分段筛
分段筛的目的是将范围[0..n-1]划分为不同的段, 并一一计算所有段中的质数。该算法首先使用简单筛来查找小于或等于√(n)的素数。以下是分段筛中使用的步骤。

使用简单筛子查找所有素数到" n"的平方根, 并将这些素数存储在数组" prime []"中。将找到的素数存储在数组" prime []"中。
我们需要[0..n-1]范围内的所有素数。我们将此范围划分为不同的细分, 以使每个细分的大小最大为√n
对每个细分[low..high]进行追踪
- 创建一个数组标记[high-low + 1]。这里我们只需要O(x)空间, X是给定范围内的元素数。
- 遍历在步骤1中找到的所有素数。对于每个素数, 在给定范围[low..high]中标记其倍数。

在简单筛中, 我们需要O(n)空间, 这对于大n可能不可行。这里我们需要O(√n)空间, 并且一次处理较小的范围(参考位置)
以下是上述想法的实现。
C ++

//C++ program to print print all primes smaller than //n using segmented sieve #include < bits/stdc++.h> using namespace std; //This functions finds all primes smaller than 'limit' //using simple sieve of eratosthenes. It also stores //found primes in vector prime[] void simpleSieve( int limit, vector< int> & prime) { //Create a boolean array "mark[0..n-1]" and initialize //all entries of it as true. A value in mark will //finally be false if 'p' is Not a prime, else true. bool mark[limit+1]; memset (mark, true , sizeof (mark)); for ( int p=2; p*p< limit; p++) { //If p is not changed, then it is a prime if (mark == true ) { //Update all multiples of p for ( int i=p*p; i< limit; i+=p) mark[i] = false ; } } //Print all prime numbers and store them in prime for ( int p=2; p< limit; p++) { if (mark == true ) { prime.push_back(p); cout < < p < < " " ; } } } //Prints all prime numbers smaller than 'n' void segmentedSieve( int n) { //Compute all primes smaller than or equal //to square root of n using simple sieve int limit = floor ( sqrt (n))+1; vector< int> prime; simpleSieve(limit, prime); //Divide the range [0..n-1] in different segments //We have chosen segment size as sqrt(n). int low = limit; int high = 2*limit; //While all segments of range [0..n-1] are not processed, //process one segment at a time while (low < n) { if (high> = n) high = n; //To mark primes in current range. A value in mark[i] //will finally be false if 'i-low' is Not a prime, //else true. bool mark[limit+1]; memset (mark, true , sizeof (mark)); //Use the found primes by simpleSieve() to find //primes in current range for ( int i = 0; i < prime.size(); i++) { //Find the minimum number in [low..high] that is //a multiple of prime[i] (divisible by prime[i]) //For example, if low is 31 and prime[i] is 3, //we start with 33. int loLim = floor (low/prime[i]) * prime[i]; if (loLim < low) loLim += prime[i]; /* Mark multiples of prime[i] in [low..high]: We are marking j - low for j, i.e. each number in range [low, high] is mapped to [0, high-low] so if range is [50, 100] marking 50 corresponds to marking 0, marking 51 corresponds to 1 and so on. In this way we need to allocate space only for range */ for ( int j=loLim; j< high; j+=prime[i]) mark[j-low] = false ; } //Numbers which are not marked as false are prime for ( int i = low; i< high; i++) if (mark[i - low] == true ) cout < < i < < " " ; //Update low and high for next segment low = low + limit; high = high + limit; } } //Driver program to test above function int main() { int n = 100000; cout < < "Primes smaller than " < < n < < ":n" ; segmentedSieve(n); return 0; }

Java

//Java program to print print all primes smaller than //n using segmented sieve import java.util.Vector; import static java.lang.Math.sqrt; import static java.lang.Math.floor; class Test { //This methid finds all primes smaller than 'limit' //using simple sieve of eratosthenes. It also stores //found primes in vector prime[] static void simpleSieve( int limit, Vector< Integer> prime) { //Create a boolean array "mark[0..n-1]" and initialize //all entries of it as true. A value in mark will //finally be false if 'p' is Not a prime, else true. boolean mark[] = new boolean [limit+ 1 ]; for ( int i = 0 ; i < mark.length; i++) mark[i] = true ; for ( int p= 2 ; p*p< limit; p++) { //If p is not changed, then it is a prime if (mark == true ) { //Update all multiples of p for ( int i=p*p; i< limit; i+=p) mark[i] = false ; } }//Print all prime numbers and store them in prime for ( int p= 2 ; p< limit; p++) { if (mark 【算法设计（分段筛(Segmented Sieve)介绍和代码实现）】 == true ) { prime.add(p); System.out.print(p + "" ); } } }//Prints all prime numbers smaller than 'n' static void segmentedSieve( int n) { //Compute all primes smaller than or equal //to square root of n using simple sieve int limit = ( int ) (floor(sqrt(n))+ 1 ); Vector< Integer> prime = new Vector< > (); simpleSieve(limit, prime); //Divide the range [0..n-1] in different segments //We have chosen segment size as sqrt(n). int low= limit; int high = 2 *limit; //While all segments of range [0..n-1] are not processed, //process one segment at a time while (low < n) { if (high> = n) high = n; //To mark primes in current range. A value in mark[i] //will finally be false if 'i-low' is Not a prime, //else true. boolean mark[] = new boolean [limit+ 1 ]; for ( int i = 0 ; i < mark.length; i++) mark[i] = true ; //Use the found primes by simpleSieve() to find //primes in current range for ( int i = 0 ; i < prime.size(); i++) { //Find the minimum number in [low..high] that is //a multiple of prime.get(i) (divisible by prime.get(i)) //For example, if low is 31 and prime.get(i) is 3, //we start with 33. int loLim = ( int ) (floor(low/prime.get(i)) * prime.get(i)); if (loLim < low) loLim += prime.get(i); /*Mark multiples of prime.get(i) in [low..high]: We are marking j - low for j, i.e. each number in range [low, high] is mapped to [0, high-low] so if range is [50, 100]marking 50 corresponds to marking 0, marking 51 corresponds to 1 and so on. In this way we need to allocate space only for range*/ for ( int j=loLim; j< high; j+=prime.get(i)) mark[j-low] = false ; }//Numbers which are not marked as false are prime for ( int i = low; i< high; i++) if (mark[i - low] == true ) System.out.print(i + "" ); //Update low and high for next segment low= low + limit; high = high + limit; } }//Driver method public static void main(String args[]) { int n = 100 ; System.out.println( "Primes smaller than " + n + ":" ); segmentedSieve(n); } }

Python3

# Python3 program to print all primes # smaller than n, using segmented sieve import math prime = [] # This method finds all primes # smaller than 'limit' using # simple sieve of eratosthenes. # It also stores found primes in list prime def simpleSieve(limit):# Create a boolean list "mark[0..n-1]" and # initialize all entries of it as True. # A value in mark will finally be False # if 'p' is Not a prime, else True. mark = [ True for i in range (limit + 1 )] p = 2 while (p * p < = limit):# If p is not changed, then it is a prime if (mark = = True ):# Update all multiples of p for i in range (p * p, limit + 1 , p): mark[i] = False p + = 1# Print all prime numbers # and store them in prime for p in range ( 2 , limit): if mark : prime.append(p) print (p, end = " " )# Prints all prime numbers smaller than 'n' def segmentedSieve(n):# Compute all primes smaller than or equal # to square root of n using simple sieve limit = int (math.floor(math.sqrt(n)) + 1 ) simpleSieve(limit)# Divide the range [0..n-1] in different segments # We have chosen segment size as sqrt(n). low = limit high = limit * 2# While all segments of range [0..n-1] are not processed, # process one segment at a time while low < n: if high> = n: high = n# To mark primes in current range. A value in mark[i] # will finally be False if 'i-low' is Not a prime, # else True. mark = [ True for i in range (limit + 1 )]# Use the found primes by simpleSieve() # to find primes in current range for i in range ( len (prime)):# Find the minimum number in [low..high] # that is a multiple of prime[i] # (divisible by prime[i]) # For example, if low is 31 and prime[i] is 3, # we start with 33. loLim = int (math.floor(low /prime[i]) * prime[i]) if loLim < low: loLim + = prime[i]# Mark multiples of prime[i] in [low..high]: # We are marking j - low for j, i.e. each number # in range [low, high] is mapped to [0, high-low] # so if range is [50, 100] marking 50 corresponds # to marking 0, marking 51 corresponds to 1 and # so on. In this way we need to allocate space # only for range for j in range (loLim, high, prime[i]): mark[j - low] = False# Numbers which are not marked as False are prime for i in range (low, high): if mark[i - low]: print (i, end = " " )# Update low and high for next segment low = low + limit high = high + limit # Driver Code n = 100 print ( "Primes smaller than" , n, ":" ) segmentedSieve( 100 ) # This code is contributed by bhavyadeep

//C# program to print print //all primes smaller than //n using segmented sieve using System; using System.Collections; class GFG { //This methid finds all primes //smaller than 'limit' using simple //sieve of eratosthenes. It also stores //found primes in vector prime[] static void simpleSieve( int limit, ArrayList prime) { //Create a boolean array "mark[0..n-1]" //and initialize all entries of it as //true. A value in mark will finally be //false if 'p' is Not a prime, else true. bool [] mark = new bool [limit + 1]; for ( int i = 0; i < mark.Length; i++) mark[i] = true ; for ( int p = 2; p * p < limit; p++) { //If p is not changed, then it is a prime if (mark == true ) { //Update all multiples of p for ( int i = p * p; i < limit; i += p) mark[i] = false ; } }//Print all prime numbers and store them in prime for ( int p = 2; p < limit; p++) { if (mark == true ) { prime.Add(p); Console.Write(p + " " ); } } }//Prints all prime numbers smaller than 'n' static void segmentedSieve( int n) { //Compute all primes smaller than or equal //to square root of n using simple sieve int limit = ( int ) (Math.Floor(Math.Sqrt(n)) + 1); ArrayList prime = new ArrayList(); simpleSieve(limit, prime); //Divide the range [0..n-1] in //different segments We have chosen //segment size as sqrt(n). int low = limit; int high = 2*limit; //While all segments of range //[0..n-1] are not processed, //process one segment at a time while (low < n) { if (high> = n) high = n; //To mark primes in current range. //A value in mark[i] will finally //be false if 'i-low' is Not a prime, //else true. bool [] mark = new bool [limit + 1]; for ( int i = 0; i < mark.Length; i++) mark[i] = true ; //Use the found primes by //simpleSieve() to find //primes in current range for ( int i = 0; i < prime.Count; i++) { //Find the minimum number in //[low..high] that is a multiple //of prime.get(i) (divisible by //prime.get(i)) For example, //if low is 31 and prime.get(i) //is 3, we start with 33. int loLim = (( int )Math.Floor(( double )(low / ( int )prime[i])) * ( int )prime[i]); if (loLim < low) loLim += ( int )prime[i]; /* Mark multiples of prime.get(i) in [low..high]: We are marking j - low for j, i.e. each number in range [low, high] is mapped to [0, high-low] so if range is [50, 100] marking 50 corresponds to marking 0, marking 51 corresponds to 1 and so on. In this way we need to allocate space only for range */ for ( int j = loLim; j < high; j += ( int )prime[i]) mark[j-low] = false ; }//Numbers which are not marked as false are prime for ( int i = low; i < high; i++) if (mark[i - low] == true ) Console.Write(i + " " ); //Update low and high for next segment low = low + limit; high = high + limit; } }//Driver code static void Main() { int n = 100; Console.WriteLine( "Primes smaller than " + n + ":" ); segmentedSieve(n); } } //This code is contributed by mits

输出如下：