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

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

本文概述

给定数字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)的素数。以下是分段筛中使用的步骤。

  1. 使用简单筛子查找所有素数到" n"的平方根, 并将这些素数存储在数组" prime []"中。将找到的素数存储在数组" prime []"中。
  2. 我们需要[0..n-1]范围内的所有素数。我们将此范围划分为不同的细分, 以使每个细分的大小最大为√n
  3. 对每个细分[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
 == 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#

//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

输出如下：

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

请注意, 分段筛的时间复杂度(或操作次数)与简单筛。它具有较大的'n'优势, 因为它具有更好的引用位置, 因此可以更好地由CPU进行缓存, 并且所需的内存空间也较小。

本文由Utkarsh Trivedi提供。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: