Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need to write a program that finds all perfect squares between two given numbers a and b such that the range can also be a = 1 and b = 10^15 what is the best way I can do this, how do I list down all such square numbers, is there some abstract math hidden underneath this problem?

share|improve this question
add comment

3 Answers

up vote 3 down vote accepted

One thing that makes this pretty straight forward is this: $(n+1)^2-n^2=2n+1$ Start with one, and keep on adding that.

share|improve this answer
    
what has this formula to do with the problem? –  AnkitSablok Nov 1 '13 at 15:38
    
What I said... You can start with $a$ and keep on applying the formula to obtain all of the squares, one after the next –  Chris Dugale Nov 1 '13 at 15:38
    
You can start with $1$, then add $2 * 1 + 1 = 3$ to it and get $4$, then add $2 * 2 + 1 = 5$ to it and get $9$, and so forth. btw, $10^{15}$ is outside of the "int" range so I would suggest using "long". –  2012ssohn Nov 1 '13 at 15:39
    
I don't understand the part keep on applying the formula, what does that mean can you show by an example and because there might be overflow on the computer how to remedy that? –  AnkitSablok Nov 1 '13 at 15:41
    
1,4,9. Their differences are 3,5 or 2*1+1, 2*2+1 –  Chris Dugale Nov 1 '13 at 15:44
show 3 more comments

Here's some code (pretty much C/C++) to implement Chris Dugale's answer:

long i = 1;
for (long n = i*i; i < k; i++) {
  n += 2i + 1;
  printf("%l\n", n);
}

The idea is that $(n+1)^2=n^2+2n+1$, so to get $(n+1)^2$ from $n^2$, just add $2n+1$ to it. Then, to get $(n+2)^2$ from $(n+1)^2$ you add $2n+3$, and so on...

share|improve this answer
    
what should the value of k be if I need to find all the perfect squares between a = 20 b = 10^6 ? how do you decide that –  AnkitSablok Nov 1 '13 at 16:02
    
That's an unusual set of limits, but then you would say $n=20,i=20,k=10^3=1000.$ –  abiessu Nov 1 '13 at 16:05
    
I don't get how are you deciding the value of k and n, in general if you want to find the square numbers between [a,b] how does one go about it using the snippet you provided, I executed the snippet but it yields wrong result for a = 1 and b = 10 and a= 100 and b = 10000 –  AnkitSablok Nov 1 '13 at 16:23
    
My bad, I should have said $n=25,i=5$ as the first square inside the range. For $a=1$ you would have $n=1,i=1$ and for $a=100$ you would have $n=100,i=10$. For the $b$ values, I picked the largest integer less than or equal to the square root, so for $b=10,k=3$ and for $b=10000,k=100$. I have updated the C-ish code in my answer to have $n$ begin at the correct point. –  abiessu Nov 1 '13 at 16:46
add comment

You can do it much easily by first calculating the square roots of $a$ and $b$. And count the number of integers between those square roots (just subtract one from the other). But be careful when one of $a$ and $b$ is a square itself.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.