Originally Posted by
Zaphod_b
Well, for starters, you are only going to test elements on the diagonal and antidiagonal for primality, so why bother to wrap yourself around in circles generating entire arrays? Just look at the corners....
On the other hand, if you have some reason to actually generate the spirals incrementally, you could try something like
//
//Direction of the result is clockwise out from the center.
//
public static int [][] nextCWSpiral(int [][] oldSpiral) throws IllegalArgumentException
{
int oldsiz = oldSpiral.length;
if (oldsiz < 1)
{
throw new IllegalArgumentException("Illegal input. Old spiral must have size > 0.");
}
// Length of rows and columns of new array = oldlengths+2
int newsiz = oldsiz + 2;
// A brand new array
int [][] newSpiral = new int[newsiz][newsiz];
// Just for the heck of it make sure no one throws something
// at it that won't mean anything.
for (int i = 0; i < oldSpiral.length; i++)
{
if (oldSpiral[i].length != oldsiz)
{
throw new IllegalArgumentException("Illegal input. Old spiral must be square.");
}
}
//
// Write values into new top row: Upper right is length squared,
// and that is the largest element of the new array. Working
// to the left from there means that the next result will
// spiral out from the center in a clockwise direction.
//
int newValue = newsiz*newsiz;
// Here: I'll do this one. You can do the rest
for (int j = newsiz-1; j >= 0; j--)
{
newSpiral[0][j] = newValue--;
}
// Create first column below upper left element
for (int i = whatever; condition; i++)
{
newSpiral[i][0] = newValue--;
}
// Create bottom row to the right of lower left element
for (int j = whatever; condition; j++)
{
newSpiral[newsiz-1][j] = newValue--;
}
// Create last column between lower right and upper right elements
for (int i = whatever; condition; i--)
{
newSpiral[i][newsiz-1] = newValue--;
}
// Now copy old array to the inner cells of the new
for (int i = whatever; condition; i++)
{
for (int j = whatever; condition; j++)
{
newSpiral[i][j] = oldSpiral[i-1][j-1];
}
}
return newSpiral;
}
Then with something like the following in main():
public static void main(String [] args)
{
//
// Maybe you want to try your old stuff here, for comparison
//
int [][] array = {{1}}; // A new 1x1 array with array[0][0] = 1
System.out.println("Starting with manually generated array.");
System.out.printf("%d x %d:\n", 1, 1);
System.out.println(toString(array));
//
// Note that i is not used by the function; it's just for reference.
//
// Starting with 1x1 array whose element value is 1,
// each application of the function gives another "layer" of
// the spiral array.
System.out.println("Loop calls nextCWSpiral() repeatedly...\n");
for (int i = 3; i < 9; i+= 2)
{
array = nextCWSpiral(array);
System.out.printf("%d x %d:\n", i, i);
System.out.println(toString(array));
}
}
Output, if implemented with correct values for the "whatevers" and "conditions" in the nextCWSpiral function:
Starting with manually generated array.
1 x 1:
1
Loop calls nextCWSpiral() repeatedly...
3 x 3:
7 8 9
6 1 2
5 4 3
5 x 5:
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
7 x 7:
43 44 45 46 47 48 49
42 21 22 23 24 25 26
41 20 7 8 9 10 27
40 19 6 1 2 11 28
39 18 5 4 3 12 29
38 17 16 15 14 13 30
37 36 35 34 33 32 31
Of course, if your interest is only in Euler 58, you don't need all of the iterations of the array itself, since you are only going to check the new corner values each time and add the number of primes to a running total. (But I said that already.)
In fact, the Project Euler problem statement shows an array that spirals counterclockwise out from the center with the largest element in the lower right corner of the array instead of the way that your example (and my code, which was based on your example) shows. That would be just as easy if you really wanted it However (and I hate to repeat myself, yet again) the number of primes on the diagonals depends only on the corner values of each new array as you generate it, so the Euler answer would be the same.
Cheers!
Z
LinkBack URL
About LinkBacks
Making number spirals
Reply With Quote
Related threads:
Re: Making number spirals
