算法设计：分段筛(打印范围内的素数)

2021年3月24日15:05:52 发表评论 918 次浏览

本文概述

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)

输出如下：

11  13  17  19  23  29  31  37  41  43  47  
53  59  61  67  71  73  79  83  89  97

分段筛(如果范围的"高"值太高且范围也大怎么办)

考虑给定的高值如此之高以至于sqrt(high)或O(high-low + 1)都无法容纳在内存中的情况。如何在范围内找到素数。对于这种情况, 我们仅针对内存中的限制运行步骤1(简单筛分)。然后, 我们将给定范围划分为不同的细分。对于每个分段, 我们将第2步和第3步视为当前分段的终点, 将低点和高端作为终点。在运行下一个段之前, 我们将当前段的质数添加到prime []中。

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