logo

TechCodeview

Druk priemgetallen in een bepaald bereik af met behulp van C++ STL

Genereer alle priemgetallen tussen twee gegeven getallen. De taak is om priemgetallen in dat bereik af te drukken. De Zeef van Eratosthenes is een van de meest efficiënte manieren om alle priemgetallen kleiner dan n te vinden, waarbij n kleiner is dan ongeveer 10 miljoen. Voorbeelden:

  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

Aanbevolen: los het op OEFENING eerst voordat u verdergaat met de oplossing.

Het idee is om Sieve of Eratosthenes als subroutine te gebruiken. Zoek eerst priemgetallen in het bereik van 0 tot begin en sla deze op in een vector. Zoek op dezelfde manier priemgetallen in het bereik van 0 tot eind en sla deze op in een andere vector. Neem nu het ingestelde verschil van twee vectoren om het vereiste antwoord te verkrijgen. Verwijder eventuele extra nullen in de 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; }

Uitvoer 
53 59 61 67 71 73 79 83 89 97

Tijdcomplexiteit: O(NlogN) waarbij N het verschil tussen de intervallen is.
Hulpruimte: O(N) om Booleaanse vector op te slaan.



 

Quiz maken