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

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

本文概述

给定数字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: