CODEWITHSUNDEEP
c++algorithm
Mite Ristovski
Mite Ristovski

Reputation: 231

Perfect Squares between two numbers

Is there any fast way in C (below 1 sec) to find the number of perfect squares between two numbers. For ex. for 1 <-> 10 we have 2 perfect squares 4 and 9. But what about between 1<->2^60 or some other bigger number.

This is slow

while(i*i<=n)
{
    sum+=i==((long long)(sqrt(i*i)));
    i++;
}

where n is lets say 2^60 and we start with i=2.

Upvotes: 10

Views: 10141

Answers (5)

Jackie
Jackie

Reputation: 91

Language-agnostic formula to get the number of perfect squares in range [a, b] inclusive, as long as the basic math function sqrt, ceil and floor are provided by the standard lib.

cnt = int(floor(sqrt(b))) - int(ceil(sqrt(a))) + 1

Upvotes: 0

Erix
Erix

Reputation: 51

Don't iterate. The equation:

floor(sqrt(b)) - ceil(sqrt(a)) + 1

gives the number of perfect squares in the interval from a up to b inclusive.

https://en.wikipedia.org/wiki/Intermediate_value_theorem

Upvotes: 5

Dhruv
Dhruv

Reputation: 159

if(n1 is a perfect square)      
    x=(int)sqrt(n2)-(int)sqrt(n1)+1;  
else   
    x=(int)sqrt(n2)-(int)sqrt(n1);

Upvotes: 0

user85109
user85109

Reputation:

Its trivial. Assume you have two endpoints, a & b, with a < b.

  1. What is the next perfect square after a? Hint, what is sqrt(a)? What would rounding up do?

  2. What is the largest perfect square that does not exceed b? Hint, what is sqrt(b)? Again, how would rounding help here?

Once you know those two numbers, counting the number of perfect squares seems truly trivial.

By the way, be careful. Even the sqrt of 2^60 is a big number, although it will fit into a double. The problem is that 2^60 is too large to fit into a standard double, since it exceeds 2^53. So beware precision issues.

Upvotes: 12

Benjamin Lindley
Benjamin Lindley

Reputation: 103733

x = (int)sqrt(n2) - (int)sqrt(n1);

Upvotes: 41

Related Questions