﻿ Project Euler Problem 58
You are on the Home/Other Tutorials/Project Euler/Problem 58 page Share Your

# Project Euler - Problem 58

## Problem description

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

## Solution

While the spiral in this case is anti-clockwise, the calculation of the elements on the diagonals is identical to that for Euler 28.  This can be done in Excel with the help of the IsPrime user defined function as long as the numbers in question are not longer than 15 digits in length.  Alternatively, one can use VBA and the decimal data type that supports 29 significant digits.

```Function IsPrime(aNbr As Variant) As Boolean
Dim K As Long
K = 1
If aNbr = 2 Or aNbr = 3 Then IsPrime = True: Exit Function
If aNbr Mod 2 = 0 Or aNbr Mod 3 = 0 Then IsPrime = False: Exit Function
Do While 6 * K - 1 <= Sqr(aNbr)
If aNbr Mod (6 * K - 1) = 0 Or aNbr Mod (6 * K + 1) = 0 Then _
IsPrime = False: Exit Function
K = K + 1
Loop
IsPrime = True
End Function
Sub Euler058()
Dim SqrLen As Long, CellVal As Variant, PrevCellVal As Variant, _
NbrPrimes As Long, NbrDiagCells As Long, _
ProcTime As Single
ProcTime = Timer
CellVal = CDec(3): PrevCellVal = CDec(1)
NbrPrimes = 3: NbrDiagCells = 5
SqrLen = 3
Do While NbrPrimes / NbrDiagCells >= 0.1
SqrLen = SqrLen + 2
NbrDiagCells = 2 * SqrLen - 1
Dim Temp As Variant
Temp = CellVal + (CellVal - PrevCellVal + 8)
If IsPrime(Temp) Then NbrPrimes = NbrPrimes + 1
If IsPrime(Temp + ((SqrLen - 3) / 2 + 1) * 2) Then NbrPrimes = NbrPrimes + 1
If IsPrime(Temp + ((SqrLen - 3) / 2 + 1) * 4) Then NbrPrimes = NbrPrimes + 1
If IsPrime(Temp + ((SqrLen - 3) / 2 + 1) * 6) Then NbrPrimes = NbrPrimes + 1
PrevCellVal = CellVal: CellVal = Temp
Loop
Debug.Print SqrLen, Timer - ProcTime
End Sub```

In Excel, start with the layout for Euler 28 and add the extra columns shown below.  Copy the contents of row 4 as far down as necessary to get a value < 10% in column I.  Use conditional formatting for column I to spot the instances with under 10% of primes.   