算法设计（分段筛(打印范围内的素数)） _数据结构

本文概述

C ++
python

给定范围[低, 高], 请打印该范围内的所有素数？例如, 如果给定范围为[10, 20], 则输出为11、13、17、19。
一种简单的方法是从低到高运行一个循环，并检查每个数字的质数。
一种更好的方法是使用Eratosthenes筛网预计算最大限度的素数，然后打印范围内的所有素数。
上面的方法看起来不错, 但是请考虑输入范围[50000, 55000]。上述Sieve方法会预先计算2至50100的质数。这会浪费内存和时间。以下是基于分段筛的方法。
分段筛(背景)
以下是了解分段筛网工作原理的基本步骤

使用简单筛子查找所有不超过预定义限制的质数(在下面的代码中使用"高"的平方根), 并将这些质数存储在数组" prime []"中。基本上, 我们将简单筛选称为极限, 不仅找到质数, 还将它们放在单独的数组prime []中。
创建一个数组标记[high-low + 1]。这里我们只需要O(n)空间?是给定范围内的元素数。
遍历在步骤1中找到的所有素数。对于每个素数, 在给定范围[low..high]中标记其倍数。

因此, 与简单筛不同, 我们不检查每个小于整数高的平方根的数的所有倍数, 我们只检查在步骤1中找到的素数的倍数。我们不需要O(high)空间, 我们需要O (sqrt(high)+ n)空间。
以下是上述想法的实现。
C ++

// C++ program to print // print all primes in a range // using concept of Segmented Sieve #include < bits/stdc++.h> using namespace std; // This functions finds all // primes smaller than limit // using simple sieve of eratosthenes. // It stores found // primes in vector prime[] void simpleSieve( int limit, vector< int > & prime) { bool mark[limit + 1]; memset (mark, false , sizeof (mark)); for ( int i = 2; i < = limit; ++i) { if (mark[i] == false ) { // If not marked yet, then its a prime prime.push_back(i); for ( int j = i; j < = limit; j += i) mark[j] = true ; } } } // Finds all prime numbers // in given range using // segmented sieve void primesInRange( int low, int high) {// Comput all primes smaller or equal to // square root of high using simple sieve int limit = floor ( sqrt (high)) + 1; vector< int > prime; simpleSieve(limit, prime); // Count of elements in given range int n = high - low + 1; // Declaring boolean only for [low, high] bool mark[n + 1]; memset (mark, false , sizeof (mark)); // Use the found primes by // simpleSieve() to find // primes in given 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]) int loLim = floor (low / prime[i]) * prime[i]; if (loLim < low) loLim += prime[i]; if (loLim==prime[i]) 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.Also if the current j is prime don't mark it as true.In this way we need to allocate space only for range*/ for ( int j = loLim; j < = high; j += prime[i]) if (j != prime[i]) mark[j - low] = true ; } // Numbers which are not marked // in range, are prime for ( int i = low; i < = high; i++) if (!mark[i - low]) cout < < i < < "" ; } // Driver program to test above function int main() { int low = 10, high = 100; primesInRange(low, high); return 0; }

python

# Python program to print # print all primes in a range # using concept of Segmented Sieve from math import floor, sqrt# This functions finds # all primes smaller than limit # using simple sieve of eratosthenes. # It stores found # primes in list prime[] def simpleSieve(limit, primes): mark = [ False ] * (limit + 1 )for i in range ( 2 , limit + 1 ): if not mark[i]:# If not marked yet, #then its a prime primes.append(i) for j in range (i, limit + 1 , i): mark[j] = True # Finds all prime numbers # in given range using # segmented sieve def primesInRange(low, high):# Comput all primes smaller # or equal to # square root of high # using simple sieve limit = floor(sqrt(high)) + 1 primes = list () simpleSieve(limit, primes) # Count of elements in given range n = high - low + 1# Declaring boolean only for # [low, high] mark = [ False ] * (n + 1 ) # Use the found primes by # simpleSieve() to find # primes in given range for i in range ( len (primes)):# Find the minimum number # in [low..high] that is # a multiple of prime[i] # (divisible by prime[i]) loLim = floor(low / primes[i]) * primes[i] if loLim < low: loLim + = primes[i] if loLim = = primes[i]: loLim + = primes[i] # Mark multiples of primes[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 + 1 , primes[i]): if j ! = primes[i]: mark[j - low] = True # Numbers which are not marked # in range, are prime for i in range (low, high + 1 ): if not mark[i - low]: print (i, end = " " ) # Driver program to test above function low = 10 high = 100 primesInRange(low, high)

【算法设计（分段筛(打印范围内的素数)）】输出如下：

1113171923293137414347 53596167717379838997

分段筛(如果范围的"高"值太高且范围也大怎么办)
考虑给定的高值如此之高以至于sqrt(high)或O(high-low + 1)都无法容纳在内存中的情况。如何在范围内找到素数。对于这种情况, 我们仅针对内存中的限制运行步骤1(简单筛分)。然后, 我们将给定范围划分为不同的细分。对于每个分段, 我们将第2步和第3步视为当前分段的终点, 将低点和高端作为终点。在运行下一个段之前, 我们将当前段的质数添加到prime []中。
。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。