מספר אלמנטים עם גורמים אי-זוגיים בטווח נתון

נסה את זה ב-GfG Practice ' title=

#practiceLinkDiv { display: none !חשוב; }

בהינתן טווח [ נ מ ] מצא את מספר האלמנטים שיש להם מספר אי זוגי של גורמים בטווח הנתון ( נ ו מ כָּלוּל).
דוגמאות:

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

תרגול מומלץ ספירת גורמים מוזרים נסה את זה!

א פתרון פשוט הוא לעבור דרך כל המספרים החל מ- נ . עבור כל מספר בדוק אם יש לו מספר זוגי של גורמים. אם יש לו מספר זוגי של גורמים, הגדל את הספירה של מספרים כאלה ולבסוף הדפס את מספר האלמנטים האלה. כדי למצוא את כל המחלקים של מספר טבעי, עיין ביעילות כל המחלקים של מספר טבעי
א פתרון יעיל זה להתבונן בתבנית. רק המספרים האלה שהם ריבועים מושלמים יש מספר אי זוגי של גורמים. הבה ננתח דפוס זה באמצעות דוגמה.
למשל ל-9 יש מספר אי-זוגי של גורמים 1 3 ו-9. ל-16 יש גם מספר אי-זוגי של גורמים 1 2 4 8 16. הסיבה לכך היא עבור מספרים שאינם ריבועים מושלמים כל הגורמים הם בצורת זוגות אבל עבור ריבועים מושלמים גורם אחד הוא יחיד והופך את הסכום לא-זוגי.
כיצד למצוא מספר ריבועים מושלמים בטווח?
התשובה היא ההבדל בין שורש ריבועי של מ ו n-1 ( לא נ )
יש הסתייגות קטנה. בתור שניהם נ ו מ הם כוללים אם נ הוא ריבוע מושלם נקבל תשובה שהיא פחות מאחת התשובה בפועל. כדי להבין זאת שקול טווח [4 36]. התשובה היא 5 כלומר המספרים 4 9 16 25 ו-36.
אבל אם נעשה (36**0.5) - (4**0.5) נקבל 4. אז כדי למנוע את השגיאה הסמנטית הזו אנחנו לוקחים n-1 .

אלגוריתמים למיון הכנסה

C++

// 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(m0.5) - (int)pow(n-10.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)m0.5) - (int)Math.pow((double)n-10.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# 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(m0.5) - Math.pow(n-10.5);  } // Driver Code  let n = 5 m = 100;  document.write('Count is ' + countOddSquares(n m));   </script>

פלט:

Count is 8

מורכבות זמן: O(1)
מרחב עזר: O(1)

להשוות לג'אווה