# 算法设计：分段筛(Segmented Sieve)介绍和代码实现

2021年4月12日11:11:46 发表评论 896 次浏览

## 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也不友好。该算法遍历数组时没有参考位置

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

## 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`````` == true )
{
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#

``````//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 )
{
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)
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``````

``````Primes smaller than 100:
2 3 5 7 11 13 17 19 23 29 31 37 41
43 47 53 59 61 67 71 73 79 83 89 97``````