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

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

## 本文概述

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

## 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``````

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