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