logo

TechCodeview

Drukājiet pirmskaitļus noteiktā diapazonā, izmantojot C++ STL

Ģenerējiet visus pirmskaitļus starp diviem dotajiem skaitļiem. Uzdevums ir izdrukāt pirmskaitļus šajā diapazonā. The Eratostena siets ir viens no efektīvākajiem veidiem, kā atrast visus pirmskaitļus, kas ir mazāki par n, kur n ir mazāks par 10 miljoniem. Piemēri:

  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

Ieteicams: lūdzu, atrisiniet to PRAKSE vispirms, pirms pāriet pie risinājuma.

Ideja ir izmantot Eratosthenes sietu kā apakšprogrammu. Vispirms atrodiet pirmskaitļus diapazonā no 0 līdz sākumam un saglabājiet to vektorā. Līdzīgi atrodiet pirmskaitļus diapazonā no 0 līdz beigām un saglabājiet citā vektorā. Tagad ņemiet divu vektoru starpību, lai iegūtu vajadzīgo atbildi. Noņemiet papildu nulles, ja tādas ir vektorā.

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; }

Izvade 
53 59 61 67 71 73 79 83 89 97

Laika sarežģītība: O(NlogN), kur N ir starpība starp intervāliem.
Palīgtelpa: O(N), lai saglabātu Būla vektoru.



 

Izveidojiet viktorīnu