[C/C++] Project Euler #28 - Number Spiral Diagonals

This program can actually work by defining the desired array, arranging the numbers, and then calculating the sum of the diagonals.

Even if you do it this way, it doesn’t take a significant amount of time.

However, when I first started writing these Project Euler posts, I focused on figuring out how to calculate more efficiently, so I tackled this problem by reducing its complexity.

If you know how to derive formulas for the sum of numbers from 1 to  N , the sum of squares, and so on, this problem can also be simplified into a single formula.

Here, the following formula is derived:

\[ \text{result} = 1 + \frac{8n(n+1)(2n+1)}{3} + 2n(n+1) + 4n \]

 

number spiral diagonals

The program based on this formula is as follows.
Again, please use this program for reference only.

//------------------------------------------------
//    Project Euler #28 - Number Spiral Diagonals
//        - by Aubrey Choi
//        - created at 2015-01-30
//------------------------------------------------
#include <stdio.h>

//#define    NUMBER    5
#define    NUMBER    1001

int main()
{
    int n = NUMBER;

    n = (n-1)/2;

    printf("Ans = %d\n", 1+8*n*(n+1)*(2*n+1)/3+2*n*(n+1)+4*n);
}