代码高尔夫：乌拉姆螺旋

Question

挑战

按字符数输出最短的代码 Ulam 螺旋，螺旋大小由用户输入指定。

乌拉姆螺旋是映射素数的一种方法。螺旋从位于中心的数字 1 开始（1 不是素数）并在其周围生成螺旋，将所有素数标记为字符“*”。非素数将被打印为空格“”。

替代文本 http://liranuna.com/junk/ulam.gif

测试用例

Input:
    2
Output:
    * *
      *
    *  
    
Input:
    3
Output:
    *   *
     * * 
    *  **
     *   
      *  
      
Input:
    5
Output:
        * *  
     *     * 
    * *   *  
       * * * 
      *  ** *
     * *     
    *   *    
     *   *   
    *     *  

代码计数包括输入/输出（即完整程序）。

Answer 1

Python - 203 个字符

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

工作原理
这个想法是用需要打印为 '*' 的 x,y 坐标填充 A
该算法从与 2 对应的单元格开始，因此避免了测试 1 素数的特殊情况。
x,y 是感兴趣的单元格
j,k 跟踪我们是否需要 inc 或 dec x 或 y 才能到达下一个单元格
s 是下一个角点 i 的值
t 跟踪 s

all(i%d for d in R(2,i)) 的增量进行素性检查

最后一行相当笨拙。它迭代所有单元格并决定是否放置空格或星号

Answer 2

MATLAB： 182 167 156 个字符

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

格式更好一点：

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

测试用例：

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

Answer 3

Golfscript - 92 个字符

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

97 个字符
~.(:S+,:R{S\-:|;R{S-:$|>' *'1/[|$.|]2/@:d|~)${$\%!},!=}%n}%

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

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

101 个字符
~:S.(+,{S(-}%:R{~):v;R{:$v>:d;' *'1/[v$.v]2/v~)${$\%!},!=}%n}%

Answer 4

C、 <罢工>208 <罢工>206 <罢工>201 <罢工>200 <罢工>199 <罢工>196 <罢工>194 <罢工>193 <罢工>194 <罢工>193 <罢工>188 <罢工>185 <罢工>183 180 176 字节

（如果删除换行符）：

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

编译时有

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

警告。这个程序很慢，因为它试除最多 2^31。但它确实产生了所需的输出：

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

在格式良好的 C 中并带有冗余的 #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?' ':'*');
        }
}

它的工作原理是将网格的坐标转换为适当的数字，然后执行素性测试，而不是以蛇状方式绘制。通过交换 x 和 y 以及“向后计数”的附加项，可以将四个“象限”的不同方程合并为一个方程。

Answer 5

Ruby 1.8.7，194 个字符

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?"\n":''}

出于某种原因，ruby1.9 需要在第 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}

Answer 6

Python - 171

drhirsch 的 C 移植到 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 
      *     *   * *   *             *  
 *     * *     *   * *                 
*     * *                     *     *  
       * *     *   *           *     * 
                  *   * *   *          
 *               *   *       *   * *   
*     *   *           * *     *        
 *   * *     * *     *     *           
* *           *           *   *     * *
   *     *   *       *     *           
    *   *         *   * *   * * *      
 * *       *     *         * *   *     
      *     *   * *               *    
                   * *     *   *   * * 
*   *   *   * *   *       *   * *      
                   * *   *             
  *       *   * *     * * *     * * *  
   * * * * * * * *   *       *         
                  * * *           *    
             *   *  ** * * *   * * *   
      *       * * *                    
               *   *                   
    *   * *   * *   *   * *   *   * *  
 *     *   *   *     *     * *   *     
                *           *          
 *         * *     *   *   *       * * 
* *     *   *           *       *     *
   *     *     *   * *                 
              * *   *     *   *     *  
   * * * *         * *     *     * *   
      *   *           * *              
 *   * *     *     *   * *           * 
  * *       *         *       *     *  
             * *   * *         *     * 
          *   *     *     *         * *
       * *     *                 *     
*   *       *           *   *     *    
                             *     *   
*   * *   *     *           *          

Answer 7

MATLAB，56 个字符，

基于 @gnovice 解决方案，通过使用 MATLAB 的 螺旋函数:)

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

测试用例：

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

Answer 8

J解决方案：197 173 165 161字节（到目前为止）
这不使用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){' *'

Answer 9

我的第一个代码高尔夫！

红宝石，309 301 283 271 265 个字符

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

Answer 10

Python 2.x，220C 213C 207C 204C 201C 198C< /del> 196C 188C

特别感谢 gnibbler 在 #stackoverflow< 中提供一些提示/code> Freenode。输出包括前导和尾随换行符。

import math
v=input()*2
w=v-1
a=['\n']*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 兼容性需要额外的字符；这使用 input< /a>，print 语句和/用于整数除法。）

Answer 11

Ruby - 158 个字符

与这个相同的算法，只是素数测试不同

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

Answer 12

Haskell - 224 个字符

(%)=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

我不是最擅长 Haskell 所以这里可能会出现更多的收缩

echo 6 | 的输出runghc ulam.hs

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

---

这是一个不同的算法（类似于@drhirsch的）不幸的是我似乎无法得到低于239个字符

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)

Answer 13

第一篇文章！（哦等等，这不是SlashDot？）

我的团队参赛作品Clojure，685 528 个字符。

(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:
        *   * *   *
 *     *         * 
  *   * *          
         * *     * 
  * *   *       *  
         * *   *   
*   * *     * * *  
 * * * *   *       
        * * *      
   *   *  ** * * * 
    * * *          
     *   *         
*   * *   *   * *  
 *   *     *     * 
      *           *
 * *     *   *   * 
  *           *    
     *   * *       
    * *   *     *  

Answer 14

不像之前的 C 条目那么漂亮，但这是我的。

注意：我发帖是因为它采用了与前一个不同的方法，主要

• 是没有坐标重新映射
• ，它给出了与测试相同的结果

• 它适用于输入 > > 9（两位数 - 没有 -47 技巧）

  enum Direction_e { dx, up, sx, dn } 方向；
  
  int main (int argc, char **argv) {
      int len = atoi(argv[1]);
      int 偏移量 = 2*len-1;
      int 大小 = 偏移量*偏移量；
      char *matrix = malloc(大小);
      int 起始位置 = 2*len*(len-1);
      矩阵[起始位置] = 1;
      int下一个=开始；
      整数计数=1；
      int i，步长= 1；
      方向=dx；
  
      对于 (;; 步骤++ )
          做 { 
              for ( i = 0 ; i < 步骤 ; i++ ) {
                  开关（方向）{
                      案例dx：
                          下一个++；
                          休息;
                      案例：
                          下一个 = 下一个 - 偏移量；
                          休息;
                      案例SX：
                          下一个 - ;
                          休息;
                      案例名称：
                          下一个 = 下一个 + 偏移量；
                  }
                  int div = ++计数；
                  做 {
                      div--;
                  } while ( 计数 % div );
                  如果（div>1）{
                      矩阵[下一个] = ' ';
                  }
                  别的 { 
                      矩阵[下一个] = '*';
                  }
                  if (count >= size) goto dontusegoto;
              }
              方向=++方向%4；
          while(方向%2);
  不要这样：
      for ( i = 0 ; i < 大小 ; i++ ) {
          putchar(矩阵[i]);
          if ( !((i+1) % offset) ) putchar('\n'); 
      }
      返回0；
  }
  

，在不可读的 C 语言中充分翻译后，变成了 339 个字符。

编译：gcc -o ulam_compr ulam_compr.c 适用于 osx

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

和 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('\n');
    }
}

这是一些输出：

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

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

Answer 15

Python - 176

这个以一长串换行符开始，并替换除行尾所需的换行符之外的所有换行符。

从中心开始，算法每一步都会观察左角。如果那里有换行符，则向左转，否则继续前进。

w=input()*2;v=w-1;a=['\n']*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
使用字符串可以避免“连接”，但由于字符串是不可变的，因此会多出一个字节

w=input()*2;v=w-1;a='\n'*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

Answer 16

Python，299 个字符：

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=['\n']*(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)

Answer 17

Lua，302 个字符

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,"\n"))

lua ulam.lua 6 的输出：

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

Answer 18

Python 284 266 256 243 242 240 char

我想尝试递归，我确信它可能会被大大缩短：

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)

根据评论中的建议进行编辑

Answer 19

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] &

用法

13 个绕组：

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