# Counting perfect squares

Below is the code I have written for counting perfect squares between a given lower and upper bound.

I am using the following concept to solve this:

Starting with 1, there are $\sqrt{m}$ square numbers up to and including $m$.

public static int CountPerfectSquares(long A, long B)
{
int count = 0;

//Proceed if lowerbound is less than upperbound
if (A < B)
{
//negative numbers are not perfect squares
if (A < 0 && B < 0) return count;

//Reset lowerbound if required
if (A <= 0) A = 1;

//Find number of squares between A & B (INCLUSIVE lower and upperbound)
//count = (int)Math.Sqrt(B) - (int)Math.Sqrt(A);  //Giving wrong count when LowerBound value is a whole square (For exp. CountPerfectSquares(1, 25))

int sqrtA = (int)Math.Sqrt(A);
int sqrtB = (int)Math.Sqrt(B);
count = sqrtB - sqrtA;
//To handle the case when lowerbound value is a perfect square number
if (A == sqrtA * sqrtA)
{
count++;
}
}

return count;
}


Can you please help me make this more efficient, if possible?

Is there any other way of handling the case when the lower bound value is a perfect square number, so that I don't have to do an extra count++?

• you are over thinking this one.
– Malachi
Commented Oct 16, 2013 at 17:00
• you can just return the Square root of the larger Number as the count, if you don't give the application perfect squares then that is a different issue
– Malachi
Commented Oct 16, 2013 at 17:02

If A was not included in the observed range, you wouldn't need the if (A == sqrtA * sqrtA) part, right? So, let's use that: instead of checking the range {A,A+1,...,B}, check the range {A-1,A,...,B}. Since you're working with integers, the two are the same:

        int sqrtA = (int)Math.Sqrt(A-1);
int sqrtB = (int)Math.Sqrt(B);
count = sqrtB - sqrtA;


A minor detail: when returning a predefined constant, I prefer writing the constant itself, not a variable initialized to that value:

        if (A < 0 && B < 0) return 0;


It seems more readable to me.

Also, I would replace two main if-s with if (B < 0 || B < A) return 0. This gives the same result, but in a cleaner way.

So, my version would be:

public static int CountPerfectSquares(long A, long B)
{
// Return zero if there are obviously no perfect squares
if (B < 0 || B < A) return 0;

// Reset the lower bound if required
if (A <= 0) A = 1;

// Find the number of perfect squares between A & B (INCLUSIVE)
return (int)Math.Sqrt(B) - (int)Math.Sqrt(A-1);  // Now giving the correct count, even when the lower bound value is a whole square (for exp. CountPerfectSquares(1, 25))
}

• +1. You could refactor this even further: public static int CountPerfectSquares(long A, long B) { if (A <= 0) A = 1; return B < 0 || B < A ? 0 : (int)Math.Sqrt(B) - (int)Math.Sqrt(A-1); } Commented Oct 16, 2013 at 12:11
• @DeeMac This would reduce readability, with no benefits (at least obvious to me). Btw, you could replace B < 0 || B < A with B < A, since you've already changed A. ;-) Commented Oct 16, 2013 at 12:14
• Nice! Fair point about the readability. Commented Oct 16, 2013 at 12:15
• really if you are being inclusive as you are, you can just return the Square root of the larger Number as the count. if you are going to give the application perfect squares and you are not going into imaginary numbers and you count 1.
– Malachi
Commented Oct 16, 2013 at 16:57
• @Vedran, Thanks a lot for the review and also for pointing out returning constant value. It does improve readability :-) Commented Oct 16, 2013 at 20:46