Sign up ×
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|cite|improve this question
How about n = int( sqrt(b) ) - int( sqrt(a) ) ? – Jakub Czaplicki yesterday

3 Answers 3

up vote 4 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|cite|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

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|cite|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

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|cite|improve this answer
Also, watch out for the case where a == b – AllDayAmazing Jun 28 at 1:34

protected by Zev Chonoles Sep 23 at 19:31

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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