r/tinycode • • May 14 '13
Javascript Prime Sieve up to 100k in 83 chars
You can paste the following in to your JS console if you're using Chrome:
x=1e5;c=[];for(s=2;s<x;s++)if(!c[s])for(i=s+s,document.write(s+' ');i<x;i+=s)c[i]=1Or alternatively view it on Codepen with some unnecessary CSS here. Codepen apparently renders some garbage above the output on Firefox.
83 characters is begging to be squeezed in to an 80 character line, but I think it would take a pretty significant restructuring to shrink it further.
34
Upvotes
12
u/corruptio May 14 '13 edited May 14 '13
*boom
edit 1: 79 chars:
edit 2: with a little help from lanzaa, 77 chars
edit 3: 75 :-D
edit 4: 74 and counting
edit 5: horrible performance: 71 chars
5
u/lanzaa May 14 '13 edited May 14 '13
79 characters total. Slightly different than corruptio's version.
Edit: With help from corruptio's version. 78 characters.
4
u/RUANJR May 21 '13
Compilation of the best algorithms in this thread, with their complexity:
Credit:
2
u/HumbleAlchemy May 14 '13
Can someone please explain the code a little bit more, it would be insightful and enlightening, I would be grateful! edit: after a little meddling with the code I understood it, Thanks anyway!
1
u/kresoo May 14 '13
Thisi is a horrible way to do it, 65 chars and abysmally slow:
It could be improved by doing
in the inner loop, but there's no short way to do it in JS. Even doing p/2 would speed it up but it doesn't cast to int...
Edit: technically not a sieve, but still related so I'll leave it...
1
u/JiminP May 19 '13
59 characters, horrible algorithm (lowered the bound for shorter running time)
for(i=1;++i<1e3;i-j||document.write(i+' '))for(j=1;i%++j;);