按字符计数输出Ulam 螺旋的最短代码，螺旋尺寸由用户输入给出。
乌拉姆螺旋线是绘制素数的一种方法。螺旋从中心的数字 1 开始（1 不是素数）并围绕它生成一个螺旋，将所有素数标记为字符 ' *'。非素数将打印为空格 ' '。
替代文字 http://liranuna.com/junk/ulam.gif
Input:
2
Output:
* *
*
*
Input:
3
Output:
* *
* *
* **
*
*
Input:
5
Output:
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
代码计数包括输入/输出（即完整程序）。
_________________________________________________________
/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 跟踪我们是否需要增加或减少 x 或 y 才能到达下一个单元
s 是 i 在下一个角落的值
t 跟踪到 s 的增量
all(i%d for d in R(2,i)) 进行素数检查
最后一行相当笨拙。它遍历所有单元格并决定是否放置空格或星号
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
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
~.(:S+,:R{S\-:|;R{S-:$|>' *'1/[|$.|]2/@:d|~)$<!^=~:$ ;:y.*4*$-y-)2d*$y-*+:$,{)$\%!},,2==}%n}%
97 个字符
~.(:S+,:R{S\-:|;R{S-:$|>' *'1/[|$.|]2/@:d|~)$<!^=~ :$;:y.*4*$-y-)2d*$y-*+.1=3*+:$,2>{$\%!},!=}%n}%
99 个字符
~.(:S+,{S-}%:R{~):|;R{:$|>' *'1/[|$.|]2/@:d|~)$<!^ =~:$;:y.*4*$-y-)2d*$y-*+.1=3*+:$,2>{$\%!},!=}%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~)$< !d^=~:$;:y.*4*$-y-)2d*$y-*+.1=3*+:$,2>{$\%!},!=}%n} %
（如果删除了换行符）：
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 以及“向后计数”的附加项合并为一个。
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}
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
回声 20 |python ulam.py
* * * * * *
* * * * * *
* * * * *
* * * * * *
* * * *
* * * * * *
* * * * * *
* * * * * * *
* * * * * * *
* * * * *
* * * * * * * *
* * * * * * *
* * * * *
* * * * * *
* * * * * * * * *
* * *
* * * * * * * * * *
* * * * * * * * * *
* * * *
* * ** * * * * * *
* * * *
* *
* * * * * * * * * * *
* * * * * * * *
* *
* * * * * * * *
* * * * * * *
* * * * *
* * * * * *
* * * * * * * * *
* * * *
* * * * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * *
* * * * * *
* *
* * * * * *
基于@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
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
我的第一个代码高尔夫！
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
(%)=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's）不幸的是我似乎无法将其低于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)
特别感谢gnibbler#stackoverflow在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)
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){' *'
与此算法相同，只是主要测试不同
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
第一次发帖！（哦等等，这不是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:
* * * *
* * *
* * *
* * *
* * * *
* * *
* * * * * *
* * * * *
* * *
* * ** * * *
* * *
* *
* * * * * *
* * * *
* *
* * * * *
* *
* * *
* * * *
不像之前的 C 条目那么漂亮，但这是我的。
注意：我发布是因为它采用与前一种不同的方法，主要是
它适用于输入> 9（两位数 - 没有-47技巧）
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('\n');
}
return 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
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
这个以一长串换行符开始，并替换所有换行符，除了行尾需要的换行符。
从中心开始，算法在每一步都在左拐角处窥视。如果那里有换行符，请向左转，否则继续前进。
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
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)
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：
* *
* *
* * * *
* * *
* * *
* ** *
* * *
* *
* * * *
* *
*
我想尝试递归，我敢肯定它可能会大大缩短：
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)
根据评论中的建议编辑
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]
