Golfscript - 92 Characters

~.(:S+,:R{S-:|;R{S-:$|> * 1/[|$.|]2/@:d|~)$<!^=~:$;:y.*4*$-y-)2d*$y-*+:$,{)$\%!},,2==}%n}%

97 characters
~.(:S+,:R{S-:|;R{S-:$|> * 1/[|$.|]2/@:d|~)$<!^=~:$;:y.*4*$-y-)2d*$y-*+.1=3*+:$,2>{$\%!},!=}%n}%

99 characters
~.(:S+,{S-}%:R{~):|;R{:$|> * 1/[|$.|]2/@:d|~)$<!^=~:$;:y.*4*$-y-)2d*$y-*+.1=3*+:$,2>{$\%!},!=}%n}%

100 characters
~:S.(+,{S(-}%:R{~):|;R{:$|> * 1/[|$.|]2/@:d|~)$<!^=~:$;:y.*4*$-y-)2d*$y-*+.1=3*+:$,2>{$\%!},!=}%n}%

101 characters
~:S.(+,{S(-}%:R{~):v;R{:$v>:d; * 1/[v$.v]2/v~)$<!d^=~:$;:y.*4*$-y-)2d*$y-*+.1=3*+:$,2>{$\%!},!=}%n}%

Python - 203 Characters

  _________________________________________________________
 /x=input();y=x-1;w=x+y;A=[];R=range;k,j,s,t=R(4)          
| for i in R(2,w*w):                                        |
|  A+=[(x,y)]*all(i%d for d in R(2,i))                      |
|  if i==s:j,k,s,t=k,-j,s+t/2,t+1                           |
|  x+=j;y+=k                                                | 
| for y in R(w):print"".join(" *"[(x,y)in A]for x in R(w))  |
 \_________________________________________________________/
           ^__^
           (oo)\_______
            (__)       )/
                ||----w |
                ||     ||


x=input();y=x-1;w=x+y
A=[];R=range;k,j,s,t=R(4)
for i in R(2,w*w): 
 A+=[(x,y)]*all(i%d for d in R(2,i))
 if i==s:j,k=k,-j;s,t=s+t/2,t+1
 x+=j;y+=k
for y in R(w):print"".join(" *"[(x,y)in A]for x in R(w))

How it works
The idea is to fill A with x,y coords that need to be printed as *
The algorithm starts at the cell corresponding to 2, so the special case of testing 1 for primality is avoided.
x,y is the cell of interest
j,k keep track of whether we need to inc or dec x or y to get to the next cell
s is the value of i at the next corner
t keeps track of the increment to s

all(i%d for d in R(2,i)) does the primality check

The last line is rather clumsy. It iterates over all the cells and decides whether to place a space or an asterisk

MATLAB: 182 167 156 characters

Script ulam.m:

A=1;b=ones(1,4);for i=0:(input(  )-2),c=b(4);b=b+i*8+(2:2:8);A=[b(2):-1:b(1);(b(2)+1:b(3)-1)  A (b(1)-1:-1:c+1) ;b(3):b(4)];end;disp(char(isprime(A)*10+32))

And formatted a little nicer:

A = 1;
b = ones(1,4);
for i = 0:(input(  )-2),
  c = b(4);
  b = b+i*8+(2:2:8);
  A = [b(2):-1:b(1); (b(2)+1:b(3)-1)  A (b(1)-1:-1:c+1) ; b(3):b(4)];
end;
disp(char(isprime(A)*10+32))

Test cases:

>> ulam
2
* *
  *
*  
>> ulam
3
*   *
 * * 
*  **
 *   
  *  
>> ulam
5
    * *  
 *     * 
* *   *  
   * * * 
  *  ** *
 * *     
*   *    
 *   *   
*     *  

C, 208 206 201 200 199 196 194 193 194 193 188 185 183 180 176 Bytes

(if newlines are removed):

main(int u,char**b){
for(int v,x,y,S=v=**++b-48;--v>-S;putchar(10))
for(u=-S;++u<S;){
x=u;y=v;v>-u^v<u?:(x=v,y=u);
x=4*y*y-x-y+1+2*(v<u)*(x-y);
for(y=1;x%++y;);
putchar(y^x?32:42);}}

Compiled with

> gcc -std=c99 -o ulam ulam.c

Warning. This program is slow, because is does a trial division up to 2^31. But is does produce the required output:

    * *
 *     *
* *   *
   * * *
  *  ** *
 * *
*   *
 *   *
*     *

In nicely formatted C and with redundant #includes:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv) {

    int u,v,x,y,d,S = atoi(argv[1]);

    /* v is the y coordinate of grid */
    for (v=S; v>=-S; --v)

        /* u is the x coordinate. The second operand (!putchar...) of the boolean or
         * is only ececuted a a end of a x line and it prints a newline (10) */
        for (u=-S; u<=S || !putchar(10); ++u) {

            /* x,y are u,v after "normalizing" the coordintes to quadrant 0
               normalizing is done with the two comparisions, swapping and and
               an additional term later */
            d = v<u;
            x=u;
            y=v;

            if (v<=-u ^ d) {
                x=v;
                y=u;
            }

            /* reuse x, x is now the number at grid (u,v) */
            x = 4*y*y -x-y+1 +2*d*(x-y);   

           /* primality test, y resused as loop variable, won t win a speed contest */
            for (y=2; y<x && x%y; ++y)
                 ;

            putchar(y!=x?   : * );
        }
}

It works by transforming the coordinates of the grid to the appropriate number and then performing the primality test, intead of drawing in a snake-like manner. The different equations for the four "quadrants" can be collapsed into one with swapping x and y and an additional term for "backward counting".

Ruby 1.8.7, 194 chars

n=2*gets.to_i-1
r=n**2
l,c=[nil]*r,r/2
r.times{|i|l[c]=i+1;c=i==0||l[c-n]&&!l[c+1]?c+1:l[c-1]&&!l[c-n]?c-n:l[c+n]?c-1:c+n}
r.times{|i|print"1"*l[i]!~/^1?$|^(11+?)1+$/? * :   ,i%n==n-1?"
":  }

For some reason, ruby1.9 wants another space on line 4:

r.times{|i|l[c]=i+1;c=i==0||l[c-n]&&!l[c+1]?c+1:l[c-1]&&!l[c-n]?c-n :l[c+n]?c-1:c+n}

Python - 171

drhirsch s C ported to python.

S=input();R=range(-S+1,S)
for w in R:
 p="";v=-w
 for u in R:d=v<u;x,y=[(u,v),(v,u)][(w>=u)^d];x=4*y*y-x-y+1+2*d*(x-y);p+=" *"[(x>1)*all(x%f for f in range(2,x))]
 print p

echo 20 |python ulam.py 
      *     *   * *   *             *  
 *     * *     *   * *                 
*     * *                     *     *  
       * *     *   *           *     * 
                  *   * *   *          
 *               *   *       *   * *   
*     *   *           * *     *        
 *   * *     * *     *     *           
* *           *           *   *     * *
   *     *   *       *     *           
    *   *         *   * *   * * *      
 * *       *     *         * *   *     
      *     *   * *               *    
                   * *     *   *   * * 
*   *   *   * *   *       *   * *      
                   * *   *             
  *       *   * *     * * *     * * *  
   * * * * * * * *   *       *         
                  * * *           *    
             *   *  ** * * *   * * *   
      *       * * *                    
               *   *                   
    *   * *   * *   *   * *   *   * *  
 *     *   *   *     *     * *   *     
                *           *          
 *         * *     *   *   *       * * 
* *     *   *           *       *     *
   *     *     *   * *                 
              * *   *     *   *     *  
   * * * *         * *     *     * *   
      *   *           * *              
 *   * *     *     *   * *           * 
  * *       *         *       *     *  
             * *   * *         *     * 
          *   *     *     *         * *
       * *     *                 *     
*   *       *           *   *     *    
                             *     *   
*   * *   *     *           *          

MATLAB, 56 characters

based on @gnovice solution, improved by using MATLAB s spiral function :)

disp(char(isprime(flipud(spiral(2*input(  )-1)))*10+32))

Test Cases:

>> disp(char(isprime(flipud(spiral(2*input(  )-1)))*10+32))
2
* *
  *
*  
>> disp(char(isprime(flipud(spiral(2*input(  )-1)))*10+32))
3
*   *
 * * 
*  **
 *   
  *  
>> disp(char(isprime(flipud(spiral(2*input(  )-1)))*10+32))
5
    * *  
 *     * 
* *   *  
   * * * 
  *  ** *
 * *     
*   *    
 *   *   
*     *  

J solution: 197 173 165 161 bytes (so far)
this does not use the method mentioned in the comments to the OP

p=:j./<.-:$g=:1$~(,])n=:<:+:".1!:1]3
d=:j.r=:1
(m=:3 : if.y<*:n do.if.0=t=:<:t do.d=:d*0j1[t=:<.r=:r+0.5 end.m>:y[g=:y(<+.p=:p+d)}g end. )t=:2
1!:2&2(1 p:g){  * 

My first code golf!

Ruby, 309 301 283 271 265 characters

s=gets.to_i;d=s*2-1;a=Array.new(d){   *d}
e=d**2;p= * *e;2.upto(e){|i|2.upto(e/i){|j|p[i*j-1]=   }};p[0]=   
s.times{|i|k=s-i-1;l=2*i;m=l+1;o=l-1
m.times{|j|n=j+k;a[k][n]=p[l**2-j];a[n][k]=p[l**2+j];a[k+l][n]=p[m**2-m+j]}
l.times{|j|a[j+k][k+l]=p[o**2+o-j]}}
puts a

Python 2.x, 220C 213C 207C 204C 201C 198C 196C 188C

Special thanks to gnibbler for some hints in #stackoverflow on Freenode. Output includes a leading and trailing newline.

import math
v=input()*2
w=v-1
a=[ 
 ]*w*v
p=w*v/2
for c in range(1,w*w):a[p]=  * [(c>1)*all(c%d for d in range(2,c))];x=int(math.sqrt(c-1));p+=(-1)**x*((x*x<c<=x*x+x)*w+1)
print  .join(a)

(Python 3 compatibility would require extra chars; this uses input, the print statement and / for integer division.)

Ruby - 158 Characters

Same algorithm as this one, just the prime test is different

p=(v=(w=gets.to_i*2)-1)*w/2-1
a= 
 *v*w
d=0
(v*v).times{|i|a[p]="1"*(i+1)!~/^1?$|^(11+?)1+$/?42:32;d=(a[p+(z=[w,-1,-w,1])[d-1]]<32)?(d-1):d%4;p+=z[d]}
puts a

Haskell - 224 characters

(%)=zipWith(++)
r x=[x]
l 1=r[1]
l n=r[a,a-1..b]++(m r[a+1..]%l s%m r[b-1,b-2..])++r[d-s*2..d]where{d=(n*2-1)^2;b=d-s*6;a=d-s*4;s=n-1}
p[_]= * 
p _=   
i n=p[x|x<-[2..n],n`mod`x==0]
m=map
main=interact$unlines.m(m i).l.read

i m not the best at haskell so there is probably some more shrinkage that can occur here

output from echo 6 | runghc ulam.hs

*   *      
     * *   
* *     * *
 * *   *   
    * * *  
   *  ** * 
* * *      
 *   *     
* *   *   *
 *     *   
  *        

this is a different algorithm (similar to @drhirsch s) unfortunately i cannot seem to get it below 239 characters

p[_]= * 
p _=   
main=interact$unlines.u.read
i n=p[x|x<-[2..n],n`mod`x==0]
u(n+1)=map(map(i.f.o).zip[-n..n].replicate((n+1)*2-1))[n,n-1..(-n)]
f(x,y,z)=4*y*y-x-y+1+if z then 2*(x-y)else 0
o(u,v)=if(v> -u)==(v<u)then(v,u,v<u)else(u,v,v<u)

First post! (oh wait, this isn t SlashDot?)

My entry for Team Clojure, 685 528 characters.

(defn ulam[n] (let [z (atom [1 0 0 {[0 0] " "}])
m [[0 1 1 0][2 -1 0 -1][2 0 -1 0][2 0 0 1][2 0 1 0]]
p (fn [x] (if (some #(zero? (rem x %)) (range 2 x)) " " "*"))]
(doseq [r (range 1 (inc n)) q (range (count m)) [a b dx dy] [(m q)]
s (range (+ (* a r) b))]
(let [i (inc (first @z)) x (+ dx (@z 1)) y (+ dy (@z 2))]
(reset! z [i x y (assoc (last @z) [x y] (p i))])))
(doseq [y (range (- n) (inc n))] (doseq [x (range (- n) (inc n))]
(print ((last @z) [x y]))) (println))))
(ulam (dec (.nextInt (java.util.Scanner. System/in))))---

Input:
5
Output:
    * *  
 *     * 
* *   *  
   * * * 
  *  ** *
 * *     
*   *    
 *   *   
*     *  

Input:
10
Output:
        *   * *   *
 *     *         * 
  *   * *          
         * *     * 
  * *   *       *  
         * *   *   
*   * *     * * *  
 * * * *   *       
        * * *      
   *   *  ** * * * 
    * * *          
     *   *         
*   * *   *   * *  
 *   *     *     * 
      *           *
 * *     *   *   * 
  *           *    
     *   * *       
    * *   *     *  

Not as beautiful as the previous C entry, but here s mine.

note: I m posting because it takes a different approach than the previous one, mainly

• there s no coordinate remapping
• it gives the same results as the tests

• it works with input > 9 (two digits - no -47 trick)

  enum directions_e { dx, up, sx, dn } direction;
  
  int main (int argc, char **argv) {
      int len = atoi(argv[1]);
      int offset = 2*len-1;
      int size = offset*offset;
      char *matrix = malloc(size);
      int startfrom = 2*len*(len-1);
      matrix[startfrom] = 1;
      int next = startfrom;
      int count = 1;
      int i, step = 1;
      direction = dx ;
  
      for (;; step++ )
          do { 
              for ( i = 0 ; i < step ; i++ ) {
                  switch ( direction ) {
                      case dx:
                          next++;
                          break;
                      case up:
                          next = next - offset;
                          break;
                      case sx:
                          next--;
                          break;
                      case dn:
                          next = next + offset;
                  }
                  int div = ++count;
                  do {
                      div--;
                  } while ( count % div );
                  if ( div > 1 ) {
                      matrix[next] =    ;
                  }
                  else { 
                      matrix[next] =  * ;
                  }
                  if (count >= size) goto dontusegoto;
              }
              direction = ++direction % 4;
          } while ( direction %2);
  dontusegoto:
      for ( i = 0 ; i < size ; i++ ) {
          putchar(matrix[i]);
          if ( !((i+1) % offset) ) putchar( 
   ); 
      }
      return 0;
  }
  

which, adequately translated in unreadable C, becomes 339 chars.

compile with: gcc -o ulam_compr ulam_compr.c works on osx

i686-apple-darwin9-gcc-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5465)

and debian Lenny.

main(int a,char**v){
    int l=atoi(v[1]),o=2*l-1,z=o*o,n=2*l*(l-1),c=1,i,s=1,d;
    char*m=malloc(z);
    m[n]=1;
    for(;;s++)do{
            for(i=0;i<s;i++){
                if(d==0)n++;
                else if(d==1)n-=o;
                else if(d==2)n--;
                else n+=o;
                int j=++c;
                while(c%--j);
                if(j>1)m[n]=   ;else m[n]= * ;
                if(c>=z)goto g;
            }d=++d%4;}while(d%2);
g:for(i=0;i<z;i++){
        putchar(m[i]);
        if(!((i+1)%o))putchar( 
 );
    }
}

Here is some output:

    $ ./ulam_compr 3
*   *
 * * 
* **
 *   
  *  

    $ ./ulam_compr 5
    * *  
 *     * 
* *   *  
   * * * 
  * ** *
 * *     
*   *    
 *   *   
*     *  

Python - 176

This one starts with a big long list of newline characters and replaces all of them except for the ones that are needed at the end of the lines.

Starting at the centre, the algorithm peeps around the lefthand corner at each step. If there is a newline character there, turn left otherwise keep going forward.

w=input()*2;v=w-1;a=[ 
 ]*v*w;p=w/2*v-1;d=0;z=[w,-1,-w,1]
for i in range(v*v):a[p]=  * [i and all((i+1)%f for f in range(2,i))];d=d%4-(a[p+z[d-1]]<   );p+=z[d]
print"".join(a)

Python - 177
Using a string avoids "join" but ends up one byte longer since the string is immutable

w=input()*2;v=w-1;a= 
 *v*w;p=w/2*v-1;d=0;z=[w,-1,-w,1]
for i in range(v*v):a=a[:p]+  * [i and all((i+1)%f for f in range(2,i))]+a[p+1:];d=d%4-(a[p+z[d-1]]<   );p+=z[d]
print a

Python, 299 characters:

from sys import *
def t(n):
 if n==1:return    
 for i in range(2,n):
  if n%i==0:return    
 return  * 
i=int(stdin.readline())
s=i*2-1
o=[ 
 ]*(s+1)*s
c=1
g=2
d=0
p=(s+2)*(i-1)
for n in range(s**2):
 o[p]=t(n+1);p+=[1,-s-1,-1,s+1][d%4];g-=1
 if g==c:d+=1
 if g==0:d+=1;c+=1;g=2*c
print   .join(o)

Lua, 302 characters

s=...t={" "}n=2 function p()for j=2,n-1 do if n%j==0 then n=n+1 return" "end
end n=n+1 return"*"end for i=2,s do for k=#t,1,-1 do t[k+1]=t[k]..p()end
t[1]=""for k=1,i*2-1 do t[1]=p()..t[1]end for k=2,#t do t[k]=p()..t[k]end
t[#t+1]=""for k=1,i*2-1 do t[#t]=t[#t]..p()end end print(table.concat(t,"
"))

Output from lua ulam.lua 6:

*   *      
     * *   
* *     * *
 * *   *   
    * * *  
   *  ** * 
* * *      
 *   *     
* *   *   *
 *     *   
  *        

Python 284 266 256 243 242 240 char

I wanted to try recursion, I m sure it may be heavily shortened:

r=range
def f(n):
 if n<2:return[[4]]
 s=2*n-1;z=s*s;c=[r(z-2*s+2,z-3*s+2,-1)];e=1
 for i in f(n-1):c+=[[c[0][0]+e]+i+[c[0][-1]-e]];e+=1
 c+=[r(z-s+1,z+1)];return c
for l in f(input()):print  .join(  * [all(x%f for f in r(2,x))]for x in l)

edited under suggestion in comments

Mathematica 243

l = Length; t = Table; f = Flatten;
h@m_ := With[{x = l@m[[1]], y = l@m}, f[{{Reverse@t[w + y + (x y), {w, x + 2}]}, 
  t[f[{(x y) + x + y + 2 + w, m[[w]], (x y) + y - w + 1}], {w, y}], 
  {t[2 + y + x + y + w + (x y), {w, x + 2}]}}, 1]];
m_~g~z_ := Nest[h, m, z] /. {_?PrimeQ -> "[Bullet]", _Integer -> ""};
  Grid[{{1}}~g~#, Frame -> All] &

Usage

13 windings:

Grid[{{1}}~g~#, Frame -> All] &[13]