logo

TechCodeview

Spausdinkite pirminius skaičius tam tikrame diapazone naudodami C++ STL

Sugeneruokite visus pirminius skaičius tarp dviejų nurodytų skaičių. Užduotis yra atspausdinti pirminius skaičius tame diapazone. The Eratosteno sietelis yra vienas iš efektyviausių būdų rasti visus pirminius, mažesnius už n, kur n yra mažesnis nei 10 mln. Pavyzdžiai:

  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

Rekomenduojama: išspręskite PRAKTIKA pirmiausia prieš pereinant prie sprendimo.

Idėja yra naudoti Eratosthenes sietą kaip paprogramę. Pirmiausia suraskite pirminius skaičius diapazone nuo 0 iki pradžios ir išsaugokite jį vektoriuje. Panašiai raskite pirminius skaičius diapazone nuo 0 iki pabaigos ir išsaugokite kitame vektoriuje. Dabar paimkite dviejų vektorių skirtumą, kad gautumėte reikiamą atsakymą. Pašalinkite papildomus nulius, jei tokių yra vektoriuje.

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

Išvestis 
53 59 61 67 71 73 79 83 89 97

Laiko sudėtingumas: O(NlogN), kur N yra intervalų skirtumas.
Pagalbinė erdvė: O(N), kad būtų saugomas loginis vektorius.



 

Sukurti viktoriną