Учитывая диапазон [ n , m ], найдите количество элементов, которые имеют нечетное количество факторов в данном диапазоне ( n и m включительно).
Примеры :
Ввод: n = 5, m = 100.
Выход: 8
Числа с нечетными множителями: 9, 16, 25,
36, 49, 64, 81 и 100
Ввод: n = 8, m = 65.
Выход: 6
Ввод: n = 10, m = 23500.
Выход: 150
Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.
A Simple Solution is to loop through all numbers starting from n. For every number, check if it has an even number of factors. If it has an even number of factors then increment count of such numbers and finally print the number of such elements. To find all divisors of a natural number efficiently, refer All divisors of a natural number
An Efficient Solution is to observe the pattern. Only those numbers, which are perfect Squares have an odd number of factors. Let us analyze this pattern through an example.
For example, 9 has odd number of factors, 1, 3 and 9. 16 also has odd number of factors, 1, 2, 4, 8, 16. The reason for this is, for numbers other than perfect squares, all factors are in the form of pairs, but for perfect squares, one factor is single and makes the total as odd.
How to find number of perfect squares in a range?
The answer is difference between square root of m and n-1 (not n)
There is a little caveat. As both n and m are inclusive, if n is a perfect square, we will get an answer which is less than one the actual answer. To understand this, consider range [4, 36]. Answer is 5 i.e., numbers 4, 9, 16, 25 and 36.
But if we do (36**0.5) – (4**0.5) we get 4. So to avoid this semantic error, we take n-1.
C++
#include <bits/stdc++.h>
using namespace std;
int countOddSquares( int n, int m)
{
return ( int ) pow (m,0.5) - ( int ) pow (n-1,0.5);
}
int main()
{
int n = 5, m = 100;
cout << "Count is " << countOddSquares(n, m);
return 0;
}
|
Java
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 );
}
public static void main (String[] args)
{
int n = 5 , m = 100 ;
System.out.print( "Count is " + countOddSquares(n, m));
}
}
|
Python3
def countOddSquares(n, m):
return int (m * * 0.5 ) - int ((n - 1 ) * * 0.5 )
n = 5
m = 100
print ( "Count is" , countOddSquares(n, m))
|
C#
using System;
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);
}
public static void Main ()
{
int n = 5, m = 100;
Console.Write( "Count is " + countOddSquares(n, m));
}
}
|
PHP
<?php
function countOddSquares( $n , $m )
{
return pow( $m , 0.5) -
pow( $n - 1, 0.5);
}
$n = 5; $m = 100;
echo "Count is " ,
countOddSquares( $n , $m );
?>
|
Javascript
<script>
function countOddSquares(n, m)
{
return Math.pow(m,0.5) - Math.pow(n-1,0.5);
}
let n = 5, m = 100;
document.write( "Count is " + countOddSquares(n, m));
</script>
|
Выход :
Счетчик 8
Сложность времени: O (1)
Эта статья предоставлена Divyanshu Bansal. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.
Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .