Это зависит от того, хотите ли вы сделать это в строке за строкой или в виде полного набора. Для всего файла в вектор целых чисел:
int main() {
std::vector<int> v( std::istream_iterator<int>(std::cin),
std::istream_iterator<int>() );
}
Если вы хотите иметь дело с линией в строке:
int main()
{
std::string line;
std::vector< std::vector<int> > all_integers;
while ( getline( std::cin, line ) ) {
std::istringstream is( line );
all_integers.push_back(
std::vector<int>( std::istream_iterator<int>(is),
std::istream_iterator<int>() ) );
}
}
~. (: S +,: R {S \ -: |; R {S -: $ |> '*' 1 / [| $. |] 2 / @ !.: d | ~) $ & л; ^ = ~: $ ;: у * 4 * $ - y-) 2d * $ у - * +: $ {!) $ \%} ,, 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 | ~ ) $ & л; ^ = ~:. $ у * ;: 4 * $ - у-) 2d * $ у - * + 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> {! $ \%} =}%}% п
(%)=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)
Не так красиво, как предыдущая запись С, но вот моя.
примечание: я пишу, потому что он использует другой подход, чем предыдущий, в основном
он работает с вводом> 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;
}
, который, адекватно переведенный в нечитаемый С, становится 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
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
Мой первый код в гольф!
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
на основе решения @gnovice , улучшено с помощью функции MATLAB spiral :))
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
* *
* *
* * *
* * *
* ** *
* *
* *
* *
* *
Особая благодарность 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)
(совместимость с Python 3 потребует дополнительных символов; для этого используются input
, оператор print
и /
для целых чисел] разделение.)
MATLAB: 182 strike> 167 strike> 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=...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
:
* * * * * * * * * * * * * * * ** * * * * * * * * * * * * *
Первый пост! (подождите, это не SlashDot ?)
Моя запись для Team 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:
* * * *
* * *
* * *
* * *
* * * *
* * *
* * * * * *
* * * * *
* * *
* * ** * * *
* * *
* *
* * * * * *
* * * *
* *
* * * * *
* *
* * *
* * * *
_________________________________________________________
/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))
Как это работает
Идея состоит в том, чтобы заполнить A координатами x, y, которые должны быть напечатаны как '*'
Алгоритм начинается с ячейки, соответствующей 2, поэтому особого случая проверки 1 на простоту можно избежать.
x, y - интересующая нас ячейка
j, k отслеживают, нужно ли нам увеличивать или уменьшать x или y, чтобы перейти к следующей ячейке
s - значение i в следующем углу
t отслеживает приращение s
all (i% d вместо d в R (2, i)) выполняет проверку на простоту
Последняя строка довольно неуклюжая. Он перебирает все ячейки и решает, поставить ли пробел или звездочку
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)
Я хотел попробовать рекурсию, я уверен, что она может быть сильно сокращена:
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)
отредактировано согласно предложению в комментариях
Этот начинается с большого длинного списка символов новой строки и заменяет их все, кроме тех, которые необходимы в конце строк.
Начало в центре алгоритм заглядывает в левый угол на каждом шаге. Если там есть символ новой строки, поверните налево, в противном случае продолжайте движение вперед.
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
Решение 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
C drhirsch, перенесенный на 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 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ** * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
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}
(если новые строки удалены):
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 и добавив дополнительный член для «обратного счета».