Ulam's Spiral (Prime Number Spiral)

Answer 1

One possible way to do it is to create a linear array or a List to store the numbers and use a formula to determine when the direction needs to change. As for output, I liked the example on wikipedia of drawing a black pixel for a prime and a white pixel for all other numbers.

Answer 2

Consider the lengths of each side: 1, 1, 2, 2, 3, 3, 4, 4, ...

The straightforward thing is to iterate over each side, rendering that side. You can use LOGO style rendering primitives:

Angle = 0;
x=0; y = 0;
int number = 1;
int sideLength = 1;

StartLine();
for (int side = 1; side < maxSize; side++) {
 for (int k = 0; k < sideLength; k++) {
  Forward(1);
  number++;

  if (isPrime(number)) {
   StopLine();
   Ouput(number);
   StartLine();
  }
 }
 TurnLeft();
 if (side % 2 == 0) sideLength++;
}

You might improve this by only iterating over primes on a side:

Answer 3

The following program works by directly calculating the coordinates of a number. The method NumberToPoint() performs the following mapping.

0 => (x0    , y0    )
1 => (x0 + 1, y0    )
2 => (x0 + 1, y0 - 1)
3 => (x0    , y0 - 1)
4 => (x0 - 1, y0 - 1)
5 => (x0 - 1, y0    )
6 => ...

The rest is a very simple prime number test and a small console application.

In order to save an image I would consider two solutions. If you can create a buffer for the whole image, you can just use the program below to fill the buffer.

If the buffer would be to large, I would create a method PointToNumber() and invert the calculation - the method takes two coordinates and returns the number at this point. With this method you can iterate from top to bottom and left to right and calculate the number at this point, check if it is prime, and output the pixel as you go without a buffer. But for both solutions the image size should be be known before you start, because adding pixels at the top and left is quite expensive (but of cause possible).

Questions

1. Any good ideas for converting the coefficient lookup in NumberToPoint() into rock solid math without using modulo, integer division, and sign a thousand times?
2. Any good ideas to shorten or speed up the prime number test?

Code

using System;
using System.Drawing;
using System.Linq;
using System.Threading;

namespace UlamsSpiral
{
   public static class Program
   {
      public static void Main()
      {
         Int32 width = 60;
         Int32 height = 60;

         Console.SetWindowSize(Math.Min(width, 120), Math.Min(height, 60));
         Console.SetBufferSize(width, height);
         Console.CursorVisible = false;

         Int32 limit = (Int32)Math.Pow(Math.Min(width, height) - 2, 2);

         for (Int32 n = 1; n <= limit; n++)
         {
            Point point = NumberToPoint(n - 1, width / 2 - 1, height / 2);

            Console.ForegroundColor = n.IsPrime() ? ConsoleColor.DarkBlue : ConsoleColor.DarkGray;

            Console.SetCursorPosition(point.X, point.Y);
            Console.Write('\u25A0');

            Console.SetCursorPosition(0, 0);
            Console.Write(n);

            Thread.Sleep(10);
         }

         Console.ReadLine();
      }

      private static Point NumberToPoint(Int32 n, Int32 x0, Int32 y0)
      {
         Int32[,] c = { { -1, 0, 0, -1, 1, 0 }, { -1, 1, 1, 1, 0, 0 }, { 1, 0, 1, 1, -1, -1 }, { 1, -1, 0, -1, 0, -1 } };

         Int32 square = (Int32)Math.Floor(Math.Sqrt(n / 4));

         Int32 index;
         Int32 side = (Int32)Math.DivRem(n - 4 * square * square, 2 * square + 1, out index);

         Int32 x = c[side, 0] * square + c[side, 1] * index + c[side, 2];
         Int32 y = c[side, 3] * square + c[side, 4] * index + c[side, 5];

         return new Point(x + x0, y + y0);
      }

      private static Boolean IsPrime(this Int32 n)
      {
         if (n < 3) return (n == 2);
         return Enumerable.Range(2, (Int32)Math.Sqrt(n)).All(m => n % m != 0);
      }
   }
}

Answer 4

Why not have a "generator" process/thread that creates the numbers and a "reader/display" process/thread that displays them, then you can separate the creation from the display and then the program will only really be limited by how much data the "reader/display" consumes. Since i would assume the "generator" needs a fairly constant sized set of data to work with.