C++ STL kullanarak belirli bir aralıktaki asal sayıları yazdırma
Verilen iki sayı arasındaki tüm asal sayıları üretin. Görev, bu aralıktaki asal sayıları yazdırmaktır. Eratostenes Eleği n'nin 10 milyondan küçük olduğu n'den küçük tüm asal sayıları bulmanın en etkili yollarından biridir. Örnekler:
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
Önerilen: Lütfen sorunu çözün PRATİK Çözüme geçmeden önce ilk olarak.
Fikir, Eratosthenes Eleği'ni alt program olarak kullanmaktır. Öncelikle 0 ile başlangıç arasındaki asal sayıları bulun ve bir vektörde saklayın. Benzer şekilde 0'dan sonuna kadar olan aralıktaki asal sayıları bulun ve başka bir vektörde saklayın. Şimdi gerekli cevabı elde etmek için iki vektörün küme farkını alın. Vektörde varsa fazladan sıfırları kaldırın.
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 ; }
Çıkış
53 59 61 67 71 73 79 83 89 97
Zaman Karmaşıklığı: O(NlogN) burada N, aralıklar arasındaki farktır.
Yardımcı Alan : Boolean vektörünü depolamak için O(N).
Test Oluştur
