Similar to this but in this one you need to write spiral starting from the center where:

  • space means composite number
  • .(dot) means prime number.

Size of the spiral can be given as parameter or on stdin. By size I mean side of square NxN and also N will be always odd.

  • 3
    Doesn't Ulam's spiral usually start with 1 in the middle and spiral outward, instead of spiraling inward? – PhiNotPi Jan 8 '12 at 21:32
  • Yeah, it's late so my brain is out of order. – Hauleth Jan 8 '12 at 22:17
  • By size of the spiral do you mean the number to go up to, or the number of spirals? – Gareth Jan 8 '12 at 22:24
  • Also, are there limits on the number that may be input or is it 1 to infinity? – Gareth Jan 8 '12 at 22:29
  • Square NxN and limit to 100000 – Hauleth Jan 8 '12 at 22:50

Python, 219 chars

N=input()
A={0:' '}
d=1j
x=1
for p in range(2,N*N+1):
 A[x]=' .'[all(p%i for i in range(2,p))]
 if abs(x.imag)==abs(x.real):x+=(1-1j)*(d==1);d*=1j
 x+=d
R=range(N)
for y in R:print''.join(A[x-N/2+(N/2-y)*1j]for x in R)

Works for any odd N. For example:

$ echo 9 | ./ulam.py 
    . .  
 .     . 
. .   .  
   . . . 
  .  .. .
 . .     
.   .    
 .   .   
.     .  

JavaScript (240 202 195 151 characters)

Update: Another much smaller version without function (a lot of credits to @mellamokb):

for(x=3,e=d=f=a>>1,c=2;(x&1?x&2?++e<a-d:--e>d:x&2?++f<a-d-1:--f>d)||++x&3||d--;c
++)for(g=0;g<2*a*a;z[g+=c]=1)z[c]||z.getContext("2d").fillRect(e,f,1,1)

Works with this HTML:

<script>a = 50</script>
<canvas id=z width=50 height=50></canvas>

25x25 example (zoomed in) - 800x800 example

This new version now performs well and outputs the right size (NxN) for any odd a.

Found some small improvements (195 now). Thanks @mellamokb.


Old version:

c=1;i=e=0;b={};for(d=[];c<a*a;){d.push("");for(i+=e+=2;i--;)d[Math.min(e-2,i)]+=
j();d.unshift("");for(i-=e;++i<e;)d[g=Math.max(0,i)]=j()+d[g]}x.innerHTML=d.join
("\n");function j(){if(f=!b[++c])for(h=c*c;h<2*a*a;h+=c)b[h]=1;return f?".":" "}

Currently takes variable a as input and outputs to an element with the id x:

<script>a = 50</script>
<pre id=x>

I used the Sieve of Eratosthenes for prime generation, which works really well. Output is quite slow so far though. Don't expect this to run for huge n yet.

  • I've used Math.max(0,i) trick in the past before thinking it was clever, but it's actually shorter to use a ternary: d[g=i>0?i:0]. Same with Math.min(e-2,i) which should be rewritten as d[i<e-2?i:e-2]. – mellamokb Jan 9 '12 at 21:30
  • @mellamokb: My never version doesn't use min or max anymore. But thanks for the tip; it's good to remember these minor optimizations. – copy Jan 9 '12 at 21:43
  • This is code-golf, so sacrifice a little performance to gain 3 chars: for(g=0;g<2*a*a;b[g+=c]=1); Likewise, move the whole for outside of the if and you can nix the {} for the if, saving another 2 characters :) – mellamokb Jan 9 '12 at 21:48
  • @mellamokb: wow, you're good at this. The second suggestion was even better because it can now be written as b[c]||z.getContext, saving 2 more characters. – copy Jan 9 '12 at 22:21
  • Working through some ideas. I have a few improvements to make, but I figured out this eval(["--f>d","--e>d","++f<a-d-1","++e<a-d"][x%4])||++x%4||d--;. Basically this replaces all the for(h().. and also changes the condition on the main loop to just d. Then you must define x=0 and subtract 1 from d to begin with since it's no longer in the condition. Finally, inline h() since it's now only called once, and should be able to save about 10 characters (hopefully) :). Will update with another idea that might save much more in a bit... – mellamokb Jan 10 '12 at 0:09

Golfscript - 92 Characters

Based on my answer here:

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

APL (85)

K[R↑+\(1+M-⍨N×M←⌈N÷2),(2/⍳N)/(2×N)⍴1(-N)¯1N]←K←⍳R←N×N←⎕⋄'. '[1+N N⍴K∊P/⍨P∊P∘.×P←1↓⍳R]

Explanation:

  • Generating the spiral:
    • K←⍳R←N×N←⎕: Read N from the user. The array size N×N is stored in R. K is [1..R].
    • (1+M-⍨N×M←⌈N÷2): The coordinate of the middle field.
    • (2×N)1(-N)¯1N: the delta coordinates for the next field (i.e. 1 right, up a line (so N fields to the left in a 1-dimensional array), then 1 left, then down a line.
    • (2/⍳N)/: duplicate the deltas to form an expanding spiral. 2/⍳N is 1 1 2 2 3 3 ... N N, duplicating the deltas by these values gives right up left left down down right right right...
    • R↑+\: sum these values (giving absolute coordinates) and take the first R.
    • K[...]←K: assign K to K in the order given above. We now have K in spiral order.
  • Generating the pattern:
    • P/⍨P∊P∘.×P←1↓⍳R: more or less the standard APL idiom for generating primes. P is [2..R], P∘.×P is a multiplication table for P. P∘.P therefore contains all composite numbers in the range [1..R]. P/⍨ then selects from P all values present in P∘.×P, giving a list of composite numbers.
    • 1+N N⍴K∊: this selects from K all the composite numbers, giving a binary list in spiral order where there's an 1 if the number is composite. Then add 1 so that composite numbers are 2 and noncomposite (prime) numbers are 1. This is formatted as a N by N table.
    • '. '[...]: prime numbers (1) become '.' and composites (2) become ' '.

Python - 203 Characters

Similar to my answer here:

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))

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.