logo

TechCodeview

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

Genera todos los números primos entre dos números dados. La tarea consiste en imprimir números primos en ese rango. El Tamiz 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 aproximadamente. 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

Recomendado: Resuélvelo en PRÁCTICA primero antes de pasar a la solución.

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

CPP 
// C++ STL program to print all primes // in a range using Sieve of Eratosthenes #include   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+1true);    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 startulli 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(startend);  for (auto i:ans)  cout<<i<<' ';  return 0; }

Producción 
53 59 61 67 71 73 79 83 89 97

Complejidad del tiempo: O(NlogN) donde N es la diferencia entre los intervalos.
Espacio Auxiliar: O(N) para almacenar el vector booleano.



 

Crear cuestionario