Belirli bir aralıkta tek çarpanlı elemanların sayısı
#practiceLinkDiv { görüntü: yok !önemli; } Bir aralık verildiğinde [ N M ] verilen aralıkta tek sayıda çarpana sahip olan elemanların sayısını bulun ( N Ve M dahil).
Örnekler:
Input : n = 5 m = 100 Output : 8 The numbers with odd factors are 9 16 25 36 49 64 81 and 100 Input : n = 8 m = 65 Output : 6 Input : n = 10 m = 23500 Output : 150
A Basit Çözüm 'dan başlayarak tüm sayıların arasında döngü yapmaktır. N . Her sayının çift sayıda çarpanı olup olmadığını kontrol edin. Çift sayıda faktöre sahipse, bu sayıların sayısını artırın ve son olarak bu tür öğelerin sayısını yazdırın. Bir doğal sayının tüm bölenlerini verimli bir şekilde bulmak için bkz. Bir doğal sayının tüm bölenleri
Bir Verimli Çözüm deseni gözlemlemektir. Yalnızca bu sayılar mükemmel Kareler tek sayıda faktör var. Bu modeli bir örnek üzerinden analiz edelim.
Örneğin 9'un tek sayıda çarpanı vardır 1 3 ve 9. 16'nın da tek sayıda çarpanı vardır 1 2 4 8 16. Bunun nedeni tam kareler dışındaki sayılar için tüm çarpanların çift şeklinde olması, tam kareler için ise bir çarpanın tek olması ve toplamı tek yapmasıdır.
Bir aralıktaki tam karelerin sayısı nasıl bulunur?
Cevap, karekök arasındaki farktır. M Ve n-1 ( hayır )
Küçük bir uyarı var. İkisi de N Ve M eğer kapsayıcıdır N tam kare ise gerçek cevaptan birden daha küçük bir cevap alacağız. Bunu anlamak için aralığı göz önünde bulundurun [4 36]. Cevap 5'tir, yani sayılar 4 9 16 25 ve 36'dır.
Ancak (36**0,5) - (4**0,5) yaparsak 4 elde ederiz. Bu anlamsal hatayı önlemek için şunu alırız: n-1 .
// C++ program to count number of odd squares // in given range [n m] #include using namespace std ; int countOddSquares ( int n int m ) { return ( int ) pow ( m 0.5 ) - ( int ) pow ( n -1 0.5 ); } // Driver code int main () { int n = 5 m = 100 ; cout < < 'Count is ' < < countOddSquares ( n m ); return 0 ; }
Java // Java program to count number of odd squares // in given range [n m] import java.io.* ; import java.util.* ; import java.lang.* ; class GFG { public static int countOddSquares ( int n int m ) { return ( int ) Math . pow (( double ) m 0.5 ) - ( int ) Math . pow (( double ) n - 1 0.5 ); } // Driver code for above functions public static void main ( String [] args ) { int n = 5 m = 100 ; System . out . print ( 'Count is ' + countOddSquares ( n m )); } } // Mohit Gupta_OMG <(o_0)>
Python3 # Python program to count number of odd squares # in given range [n m] def countOddSquares ( n m ): return int ( m ** 0.5 ) - int (( n - 1 ) ** 0.5 ) # Driver code n = 5 m = 100 print ( 'Count is' countOddSquares ( n m )) # Mohit Gupta_OMG <0_o>
C# // C# program to count number of odd // squares in given range [n m] using System ; class GFG { // Function to count odd squares public static int countOddSquares ( int n int m ) { return ( int ) Math . Pow (( double ) m 0.5 ) - ( int ) Math . Pow (( double ) n - 1 0.5 ); } // Driver code public static void Main () { int n = 5 m = 100 ; Console . Write ( 'Count is ' + countOddSquares ( n m )); } } // This code is contributed by Nitin Mittal.
PHP // PHP program to count // number of odd squares // in given range [n m] function countOddSquares ( $n $m ) { return pow ( $m 0.5 ) - pow ( $n - 1 0.5 ); } // Driver code $n = 5 ; $m = 100 ; echo 'Count is ' countOddSquares ( $n $m ); // This code is contributed // by nitin mittal. ?>
JavaScript < script > // JavaScript program to count number of odd squares // in given range [n m] function countOddSquares ( n m ) { return Math . pow ( m 0.5 ) - Math . pow ( n - 1 0.5 ); } // Driver Code let n = 5 m = 100 ; document . write ( 'Count is ' + countOddSquares ( n m )); < /script>
Çıkış :
Count is 8
Zaman Karmaşıklığı: Ç(1)
Yardımcı Alan: Ç(1)
