logo

TechCodeview

Imprimeix nombres primers en un rang determinat mitjançant C++ STL

Genera tots els nombres primers entre dos nombres donats. La tasca és imprimir nombres primers en aquest rang. El Sedós d'Eratostenes és una de les maneres més eficients de trobar tots els nombres primers més petits que n on n és més petit que 10 milions més o menys. Exemples:

  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

Recomanat: si us plau, resol-ho PRÀCTICA primer abans de passar a la solució.

La idea és utilitzar Sieve of Eratòstenes com a subrutina. En primer lloc, cerqueu nombres primers en el rang de 0 a començar i emmagatzemeu-lo en un vector. De la mateixa manera, trobeu nombres primers en el rang de 0 a final i emmagatzemeu-los en un altre vector. Ara prenem la diferència conjunta de dos vectors per obtenir la resposta requerida. Traieu zeros addicionals si n'hi ha al 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; }

Sortida 
53 59 61 67 71 73 79 83 89 97

Complexitat temporal: O(NlogN) on N és la diferència entre els intervals.
Espai auxiliar: O(N) per emmagatzemar vector booleà.



 

Crea un qüestionari