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.

Answer 2

I like your solution. The only suggestions I would make would be:

• Put the (i*i)<=n as the middle clause of your for loop, then it's checked earlier and you break out of the loop sooner.
• You don't need to check and see if (i*i)%2==0, since 'i' is always positive and a positive squared is always positive.
• With those two changes in mind you can get rid of the if statement in your for loop and just print.

Answer 3

Square of even is even. So, you really do not need to check it again. Following is the code, I would suggest:

for (i = 2; i*i <= n; i+=2)
     printf ("%d\t", i*i);

Answer 4

The largest value for i in your loop should be the floor of the square root of n.

The reason is that the square of any i (integer) larger than this will be greater than n. So, if you make this change, you don't need to check that i*i <= n.

Also, as others have pointed out, there is no point in checking that i*i is even since the square of all even numbers is even.

And you are right in ignoring odd i since for any odd i, i*i is odd.

Your code with the aforementioned changes follows:

#include "stdio.h"
#include "math.h"

int main () 
{
    int n,i;

    scanf("%d", &n);

    for( i = 2; i <= (int)floor(sqrt(n)); i = i+2 ) {       
        printf("%d \n",(i*i));
    }

    return 0;
}