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?

  • 1
    $\begingroup$ How about n = int( sqrt(b) ) - int( sqrt(a) ) ? $\endgroup$ – Jakub Czaplicki Oct 12 '15 at 20:33

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.

  • $\begingroup$ what has this formula to do with the problem? $\endgroup$ – AnkitSablok Nov 1 '13 at 15:38
  • $\begingroup$ What I said... You can start with $a$ and keep on applying the formula to obtain all of the squares, one after the next $\endgroup$ – RougeSegwayUser Nov 1 '13 at 15:38
  • $\begingroup$ 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". $\endgroup$ – 2012ssohn Nov 1 '13 at 15:39
  • $\begingroup$ 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? $\endgroup$ – AnkitSablok Nov 1 '13 at 15:41
  • $\begingroup$ 1,4,9. Their differences are 3,5 or 2*1+1, 2*2+1 $\endgroup$ – RougeSegwayUser Nov 1 '13 at 15:44

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.

  • $\begingroup$ Also, watch out for the case where a == b $\endgroup$ – AllDayAmazing Jun 28 '15 at 1:34

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

  • $\begingroup$ 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 $\endgroup$ – AnkitSablok Nov 1 '13 at 16:02
  • $\begingroup$ That's an unusual set of limits, but then you would say $n=20,i=20,k=10^3=1000.$ $\endgroup$ – abiessu Nov 1 '13 at 16:05
  • $\begingroup$ 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 $\endgroup$ – AnkitSablok Nov 1 '13 at 16:23
  • $\begingroup$ 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. $\endgroup$ – abiessu Nov 1 '13 at 16:46

protected by Zev Chonoles Sep 23 '15 at 19:31


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