Imprima números primos en un rango dado usando C++ STL

Genera todos los números primos entre dos números dados. La tarea es imprimir números primos en ese rango. La criba de Eratóstenes es una de las formas más eficientes de encontrar todos los números primos menores que n, donde n es menor que 10 millones más o menos.

Ejemplos:

Input : start = 50 end = 100
Output : 53 59 61 67 71 73 79 83 89 97

Input : start = 900 end = 1000
Output : 907 911 919 929 937 941 947 953 967 971 977 983 991 997

La idea es usar Tamiz de Eratóstenes como subrutina. En primer lugar, busque primos en el rango de 0 a inicio y guárdelo en un vector. De manera similar, encuentre números primos en el rango de 0 al final y guárdelos en otro vector. Ahora tome la diferencia establecida de dos vectores para obtener la respuesta requerida. Elimine los ceros adicionales si los hay en el vector.

// C++ STL program to print all primes 
// in a range using Sieve of Eratosthenes 
#include<bits/stdc++.h>
using namespace std;
  
typedef unsigned long long int ulli;
   
vector<ulli> sieve(ulli n)
{
    // Create a boolean vector "prime[0..n]" and
    // initialize all entries it as true. A value
    // in prime[i] will finally be false if i is
    // Not a prime, else true.
    vector<bool> prime(n+1,true);
       
    prime[0] = false;
    prime[1] = false;
    int m = sqrt(n);
   
    for (ulli p=2; p<=m; p++)
    {
       
        // If prime[p] is not changed, then it
        // is a prime 
        if (prime[p])
        {
            // Update all multiples of p
            for (ulli i=p*2; i<=n; i += p)
            prime[i] = false;
        }
    }
   
    // push all the primes into the vector ans
    vector<ulli> ans;
    for (int i=0;i<n;i++)
        if (prime[i])
            ans.push_back(i);
    return ans;
}
   
// Used to remove zeros from a vector using 
// library function remove_if()
bool isZero(ulli i)
{
    return i == 0;
}
   
vector<ulli> sieveRange(ulli start,ulli end)
{
    // find primes from [0..start] range
    vector<ulli> s1 = sieve(start);  
       
    // find primes from [0..end] range 
    vector<ulli> s2 = sieve(end);  
   
    vector<ulli> ans(end-start);
       
    // find set difference of two vectors and
    // push result in vector ans
    // O(2*(m+n)-1) 
    set_difference(s2.begin(), s2.end(), s1.begin(), 
                             s2.end(), ans.begin());
  
    // remove extra zeros if any. O(n)
    vector<ulli>::iterator itr =
                    remove_if(ans.begin(),ans.end(),isZero);
   
    // resize it. // O(n)
    ans.resize(itr-ans.begin());
   
    return ans;
}
   
// Driver Program to test above function
int main(void)
{ 
    ulli start = 50;
    ulli end = 100;
    vector<ulli> ans = sieveRange(start,end);
    for (auto i:ans)
        cout<<i<<' ';
    return 0;
}

Producción:

53 59 61 67 71 73 79 83 89 97

Este artículo es una contribución de Varun Thakur . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *