Fastest way to calculate all the even squares from 1 to n?

Question

I did this in c :

#include<stdio.h>

int main (void)
{
 int n,i;

 scanf("%d", &n);

 for(i=2;i<=n;i=i+2)
 {
   if((i*i)%2==0 && (i*i)<= n)
      printf("%d \n",(i*i));
 }
 return 0;
}

What would be a better/faster approach to tackle this problem?

Answer 1

Let me illustrate not only a fast solution, but also how to derive it. Start with a fast way of listing all squares and work from there (pseudocode):

max = n*n
i = 1
d = 3

while i < max:
    print i
    i += d
    d += 2

So, starting from 4 and listing only even squares:

max = n*n
i = 4
d = 5

while i < max:
    print i
    i += d
    d += 2
    i += d
    d += 2

Now we can shorten that mess on the end of the while loop:

max = n*n
i = 4
d = 5

while i < max:
    print i
    i += 2 + 2*d
    d += 4

Note that we are constantly using 2*d, so it's better to just keep calculating that:

max = n*n
i = 4
d = 10

while i < max:
    print i
    i += 2 + d
    d += 8

Now note that we are constantly adding 2 + d, so we can do better by incorporating this into d:

max = n*n
i = 4
d = 12

while i < max:
    print i
    i += d
    d += 8

Blazing fast. It only takes two additions to calculate each square.