给定范围内具有奇数因子的元素数的Python程序-yiteyi-C++库

给定范围[ N , M ]，找到给定范围内因子奇数的元素数( N 和 M 包括在内）。

null

例如：

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. 简单解决方案 就是从 N .对于每个数字，检查其因子是否为偶数。如果有偶数个因子，则增加这些数的计数，最后打印这些元素的数量。要有效地查找自然数的所有除数，请参阅自然数的所有除数

一 有效解决方案 就是观察模式。只有那些数字 完美正方形 有奇数个因素。让我们通过一个例子来分析这个模式。

例如，9有奇数个因子，1、3和9。16也有奇数个因子，1，2，4，8，16。原因是，对于除完美平方外的数字，所有因子都是成对的，但对于完美平方，一个因子是单因子，使总数为奇数。

如何在一个范围内找到完美正方形的数量？ 答案是 M 和 n-1 ( 不是n ) 有一点需要注意。兼而有之 N 和 M 包括在内，如果 N 如果是一个完美的正方形，我们将得到一个比实际答案小一的答案。为了理解这一点，考虑范围[4, 36 ]。答案是5，即数字4、9、16、25和36。但如果我们这样做（36**0.5）-（4**0.5），我们得到4。为了避免这种语义错误，我们采取 n-1 .

                     # 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))                   
                             
                     # This code is contributed by                   
                     # Mohit Gupta_OMG <0_o>                   

输出：

Count is 8

时间复杂度：O（1）

请参阅完整的文章给定范围内具有奇数因子的元素数更多细节！

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章