Getting Started With MEAN App Development with AngularJs , ExpressJs , NodeJs and MongoDB.

Finding how many numbers have odd number divisers in th range [a,b]

Given two number a and b.Count how many numbers in the range a to b(including both a and b) has odd number of divisors.

Input
First line of input contains number of test cases T.Each of the next T lines contains two number a and b.

Output
For each test case output a single line containing resulting count.

Constraints

T<=100
1<=a<=b<=10^12

Sample Input

1
2 5

Sample Output

1

Explanation

Divisors of 2:1,2
Divisors of 3:1,3
Divisors of 4:1,2,4
Divisors of 5:1,5
So only 4 has odd number of divisors which gives count as 1.

Solution ::

#include<stdio.h>
#include<math.h>
int main()
{
    int t;
    scanf("%d",&t); // Test cases
    while(t--)
    {
        long long a,b,ans=0;
        scanf("%lld%lld",&a,&b);
        long long first_root=ceil(sqrt(a));//sqrt of first perfect square in [a,b]
        long long last_root=sqrt(b);      //sqrt of last perfect square in [a,b]
        ans=last_root-first_root+1;
        printf("%lld\n",ans);
    }
    return 0;
}

Explanation ::

Because divisors of a number always exist in pairs, so if “i” is a divisor of a number “n“, then “n/i” would also be a divisor.
This means that the count of divisors usually remains even. The only situation where the count becomes odd is when

   i=n/i
=> i*i=n

i.e. when the number is a perfect square.

So our task becomes to count the number of perfect squares in range[a,b].

To find the perfect squares in range [a,b], we use the following :-

Largest number with square equal to or lesser than a = (int)sqrt(a)
First number with square in range[a,b],first_root = (int)sqrt(a), if a is perfect                                                                   square
                                                    (int)sqrt(a)+1, otherwise
Largest number with square equal to or lesser than b,last_root = (int)sqrt(b)
The count of numbers between first_root and last_root = last_root-first_root+1

TOTAL NUMBER OF DIVISERS OF A NUMBER not just prime by kishlay's  blog

------------------------------------------------------------------------------------------------------------------------

imp concept

to count the total number of divisor( not just prime) using the prime number for optimization , we calculate total number of times a prime divides the number and then multiply them.

for example in case of 12

the factors are , 1 ,2, 3,4,6,12              total of 6

the prime factors are 2 ( two times ) and 3 ( one time)

if we add one with the frequency and multiply them we get the total number of  factor( that are not just prime)