Drucken Sie Primzahlen in einem bestimmten Bereich mit C++ STL
Generieren Sie alle Primzahlen zwischen zwei gegebenen Zahlen. Die Aufgabe besteht darin, Primzahlen in diesem Bereich auszugeben. Der Sieb des Eratosthenes ist eine der effizientesten Methoden, um alle Primzahlen zu finden, die kleiner als n sind, wobei n kleiner als etwa 10 Millionen ist. Beispiele:
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
Empfohlen: Bitte lösen Sie es auf ÜBEN bevor Sie mit der Lösung fortfahren.
Die Idee ist, Sieve of Eratosthenes als Unterprogramm zu verwenden. Suchen Sie zunächst nach Primzahlen im Bereich von 0 bis Anfang und speichern Sie sie in einem Vektor. Finden Sie auf ähnliche Weise Primzahlen im Bereich von 0 bis Ende und speichern Sie sie in einem anderen Vektor. Nehmen Sie nun die Mengendifferenz zweier Vektoren, um die gewünschte Antwort zu erhalten. Entfernen Sie ggf. zusätzliche Nullen im 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 + 1 true ); 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 start ulli 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 ( start end ); for ( auto i : ans ) cout < < i < < ' ' ; return 0 ; }
Ausgabe
53 59 61 67 71 73 79 83 89 97
Zeitkomplexität: O(NlogN) wobei N die Differenz zwischen den Intervallen ist.
Hilfsraum: O(N) zum Speichern des booleschen Vektors.
Quiz erstellen
