Click here to Skip to main content
15,792,397 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
I have used:

int(math.sqrt(last) - math.sqrt(first))

for getting the answer, whereas it is not working for some test-cases. So, can anyone suggest me a fast algorithm for the above question.
Updated 17-Nov-22 14:19pm
joshrduncan2012 20-Mar-14 11:34am    
Why isn't this working for some test cases?

Have you tried searching on google for something related to this?
YvesDaoust 31-Mar-14 5:31am    
You do not specify if the first and last bounds are considered to be "between" as well.

I think you need the number of integer between the first integer after sqrt(first) and before sqrt(last).

To get the first integer after, you can use Math.Ceiling.

To get the first integer before, you can use Math.Floor.

Then the complete formula should be :
Math.Floor(Math.Sqrt(last)) - Math.Ceiling(Math.Sqrt(first)) + 1

+1 because if the first integer before last is the first integer after first, the difference will be 0 but you have 1 integer.

For example : with sqrt(first) = 2.3 and sqrt(last) = 3.2
you have 1 integer between the two numbers = 3 but Floor(3.2)=3 and Ceiling(2.3)=3
and Floor(3.2)-Ceiling(2.3) = 0.

This code is written using C#, but I'm sure you can found the floor and ceiling functions in other language.
Share this answer
Jalem Raj Rohit 20-Mar-14 12:57pm    
Thank you buddy.
This has helped me very much.
import math
N = int(input())

for i in range(0,N):
    first,last = map(int,input().split(" "))
    print(math.floor(math.sqrt(last)) - math.ceil(math.sqrt(first)) + 1)
Share this answer
The number of perfect squares between 0 and N (both inclusive), is the integer square root of N, let isqrt(N).

So the number of perfect squares between first and last (bounds inclusive), is the difference isqrt(last) - isqrt(first - 1).

The integer square root can be computed as the square root cast to int,
int(math.sqrt(last)) - int(math.sqrt(first - 1))
Share this answer

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900