Tamiz segmentado (imprimir primos en un rango)

Dado un rango [bajo, alto], ¿imprime todos los números primos en este rango? Por ejemplo, si el rango dado es [10, 20], entonces la salida es 11, 13, 17, 19.

Un enfoque ingenuo es ejecutar un ciclo de menor a mayor y verificar cada número para ver si es primo. 
Un mejor enfoque es precalcular los números primos hasta el límite máximo usando la criba de Eratóstenes y luego imprimir todos los números primos dentro del rango. 
El enfoque anterior se ve bien, pero considere el rango de entrada [50000, 55000]. el enfoque anterior de Sieve precalcularía números primos de 2 a 50100. Esto provoca una pérdida de memoria y de tiempo. A continuación se muestra el enfoque basado en tamiz segmentado.

Recomendado: Resuelva primero en » PRÁCTICA «, antes de pasar a la solución.

Tamiz segmentado (fondo) 
A continuación se muestran los pasos básicos para tener una idea de cómo funciona el tamiz segmentado 

1. Use Simple Sieve para encontrar todos los números primos hasta un límite predefinido (la raíz cuadrada de ‘alto’ se usa en el código siguiente) y almacene estos números primos en una array «principal[]». Básicamente llamamos a Simple Sieve para un límite y no solo encontramos números primos, sino que también los colocamos en una array separada primo[].
2. Cree una marca de array [alto-bajo + 1]. Aquí solo necesitamos el espacio O(n) donde n es el número de elementos en el rango dado.
3. Repita todos los números primos encontrados en el paso 1. Para cada número primo, marque sus múltiplos en el rango dado [bajo…alto].

Entonces, a diferencia del tamiz simple, no verificamos todos los múltiplos de cada número menor que la raíz cuadrada de alto, solo verificamos los múltiplos de números primos encontrados en el paso 1. Y no necesitamos espacio O (alto), necesitamos O (sqrt(alto) + n) espacio.
A continuación se muestra la implementación de la idea anterior.

#include <bits/stdc++.h>
using namespace std;
// fillPrime function fills primes from 2 to sqrt of high in chprime(vector) array
void fillPrimes(vector<int>& prime, int high)
{
    bool ck[high + 1];
    memset(ck, true, sizeof(ck));
    ck[1] = false;
    ck[0] = false;
    for (int i = 2; (i * i) <= high; i++) {
        if (ck[i] == true) {
            for (int j = i * i; j <= sqrt(high); j = j + i) {
                ck[j] = false;
            }
        }
    }
    for (int i = 2; i * i <= high; i++) {
        if (ck[i] == true) {
            prime.push_back(i);
        }
    }
}
// in segmented sieve we check for prime from range [low, high]
void segmentedSieve(int low, int high)
{
    if (low<2 and high>=2){
        low = 2;
    }//for handling corner case when low = 1 and we all know 1 is not prime no.
    bool prime[high - low + 1];
  //here prime[0] indicates whether low is prime or not similarly prime[1] indicates whether low+1 is prime or not
    memset(prime, true, sizeof(prime));
 
    vector<int> chprime;
    fillPrimes(chprime, high);
    //chprimes has primes in range [2,sqrt(n)]
     // we take primes from 2 to sqrt[n] because the multiples of all primes below high are marked by these
   // primes in range 2 to sqrt[n] for eg: for number 7 its multiples i.e 14 is marked by 2, 21 is marked by 3,
   // 28 is marked by 4, 35 is marked by 5, 42 is marked 6, so 49 will be first marked by 7 so all number before 49
  // are marked by primes in range [2,sqrt(49)]
    for (int i : chprime) {
        int lower = (low / i);
        //here lower means the first multiple of prime which is in range [low,high]
        //for eg: 3's first multiple in range [28,40] is 30         
        if (lower <= 1) {
            lower = i + i;
        }
        else if (low % i) {
            lower = (lower * i) + i;
        }
        else {
            lower = (lower * i);
        }
        for (int j = lower; j <= high; j = j + i) {
            prime[j - low] = false;
        }
    }
   
    for (int i = low; i <= high; i++) {
        if (prime[i - low] == true) {
            cout << (i) << " ";
        }
    }
}
int main()
{
    // low should be greater than or equal to 2
    int low = 2;
    // low here is the lower limit
    int high = 100;
    // high here is the upper limit
      // in segmented sieve we calculate primes in range [low,high]
   // here we initially we find primes in range [2,sqrt(high)] to mark all their multiples as not prime
   //then we mark all their(primes) multiples in range [low,high] as false
   // this is a modified sieve of eratosthenes , in standard sieve of  eratosthenes we find prime from 1 to n(given number)
   // in segmented sieve we only find primes in a given interval
  cout<<"Primes in range "<<low<<" to "<< high<<" are\n";
    segmentedSieve(low, high);
}

import math
 
# fillPrime function fills primes from 2 to sqrt of high in chprime list
def fillPrimes(chprime, high):
 
    ck = [True]*(high+1)
 
    l = int(math.sqrt(high))
    for i in range(2, l+1):
        if ck[i]:
            for j in range(i*i, l+1, i):
                ck[j] = False
                 
                 
 
    for k in range(2, l+1):
        if ck[k]:
            chprime.append(k)
 
# in segmented sieve we check for prime from range [low, high]
def segmentedSieve(low, high):
     
    chprime = list()
    fillPrimes(chprime, high)
# chprimes has primes in range [2,sqrt(n)]
# we take primes from 2 to sqrt[n] because the multiples of all primes below high are marked by these
# primes in range 2 to sqrt[n] for eg: for number 7 its multiples i.e 14 is marked by 2, 21 is marked by 3,
# 28 is marked by 4, 35 is marked by 5, 42 is marked 6, so 49 will be first marked by 7 so all number before 49
# are marked by primes in range [2,sqrt(49)]
    prime = [True] * (high-low + 1)
# here prime[0] indicates whether low is prime or not similarly prime[1] indicates whether low+1 is prime or not
    for i in chprime:
        lower = (low//i)
# here lower means the first multiple of prime which is in range [low,high]
# for eg: 3's first multiple in range [28,40] is 30        
        if lower <= 1:
            lower = i+i
        elif (low % i) != 0:
            lower = (lower * i) + i
        else:
            lower = lower*i
        for j in range(lower, high+1, i):
            prime[j-low] = False
             
             
    for k in range(low, high + 1):
            if prime[k-low]:
                print(k, end=" ")
 
 
#DRIVER CODE
#   low should be greater than or equal to 2
low = 2
#  low here is the lower limit
high = 100
# high here is the upper limit
# in segmented sieve we calculate primes in range [low,high]
# here we initially we find primes in range [2,sqrt(high)] to mark all their multiples as not prime
# then we mark all their(primes) multiples in range [low,high] as false
# this is a modified sieve of eratosthenes , in standard sieve of  eratosthenes we find prime from 1 to n(given number)
# in segmented sieve we only find primes in a given interval
print("Primes in Range %d to %d are"%(low,high))
segmentedSeive(low, high)

import java.util.*;
import java.lang.Math;
 
public class Main{
// fillPrime function fills primes from 2 to sqrt of high in chprime ArrayList   
    public static void fillPrime(ArrayList<Integer> chprime,int high)
    {
        boolean[] ck=new boolean[high+1];
        Arrays.fill(ck,true);
        ck[1]=false;
        ck[0]=false;
     
    for(int i=2;(i*i)<=high;i++)
    {
        if(ck[i]==true)
        {
            for(int j=i*i;j<=Math.sqrt(high);j=j+i)
            {
                ck[j]=false;
            }
        }
    }
    for(int i=2;i*i<=high;i++)
    {
        if(ck[i]==true)
        {
   //         cout<< i<<"\n";
           chprime.add(i);
        }
    }
}
// in segmented sieve we check for prime from range [low, high]
    public static void segmentedSieve(int low,int high)
    {
        ArrayList<Integer> chprime= new ArrayList<Integer>();
        fillPrime(chprime,high);
//chprimes has primes in range [2,sqrt(n)]
// we take primes from 2 to sqrt[n] because the multiples of all primes below high are marked by these
// primes in range 2 to sqrt[n] for eg: for number 7 its multiples i.e 14 is marked by 2, 21 is marked by 3,
// 28 is marked by 4, 35 is marked by 5, 42 is marked 6, so 49 will be first marked by 7 so all number before 49
// are marked by primes in range [2,sqrt(49)]        
         
        boolean[] prime=new boolean [high-low+1];
        Arrays.fill(prime,true);
//here prime[0] indicates whether low is prime or not similarly prime[1] indicates whether low+1 is prime or not       
        for(int i:chprime)
        {
            int lower=(low/i);
//here lower means the first multiple of prime which is in range [low,high]
//for eg: 3's first multiple in range [28,40] is 30 
            if(lower<=1)
            {
            lower=i+i;
            }
            else if(low%i!=0)
            {
            lower=(lower*i)+i;
            }
            else{
                lower=(lower*i);
            }
            for(int j=lower;j<=high;j=j+i)
            {
            prime[j-low]=false;
            }
        }
        for(int i=low;i<=high;i++)
        {
            if(prime[i-low]==true)
            {
            System.out.printf("%d ",i);
            }
        }    
    }
    public static void main(String[] args)
    {
// low should be greater than or equal to 2       
        int low=2;
// low here is the lower limit       
        int high=100;
// high here is the upper limit
// in segmented sieve we calculate primes in range [low,high]
// here we initially we find primes in range [2,sqrt(high)] to mark all their multiples as not prime
//then we mark all their(primes) multiples in range [low,high] as false
// this is a modified sieve of eratosthenes , in standard sieve of  eratosthenes we find prime from 1 to n(given number)
// in segmented sieve we only find primes in a given interval
        System.out.println("Primes in Range "+low+" to "+high+" are ");
        segmentedSieve(low,high);
    }
}

11  13  15  17  19  

Complejidad de tiempo : O(n)

Espacio Auxiliar: O(n)

Tamiz segmentado (¿Qué pasa si el valor ‘alto’ del rango es demasiado alto y el rango también es grande? 
Considere una situación en la que el valor alto dado es tan alto que ni sqrt (alto) ni O (alto-bajo + 1) pueden caber en la memoria. Cómo encontrar números primos en el rango. Para esta situación, ejecutamos el paso 1 (Simple Sieve) solo para un límite que pueda caber en la memoria. Luego dividimos el rango dado en diferentes segmentos. Para cada segmento, ejecutamos los pasos 2 y 3 considerando el alto y el bajo como puntos finales del segmento actual. Agregamos números primos del segmento actual a prime[] antes de ejecutar el siguiente segmento.
Este artículo es una contribución de Utkarsh Trivedi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.