3 ms·

Whoa! Code golf. Here is the most compact I could make it in racket in about 3 minutes: (define (erathostenes n) (let ([vec (make-vector n #t)])

by bjoli 9y ago

Whoa! Code golf. Here is the most compact I could make it in racket in about 3 minutes: (define (erathostenes n) (let ([vec (make-vector n #t)]) (for/list ([i (in-range i n)] #:when (vector-ref vec i)) (for ([j (in-range (* i i) n i)]) (vector-set! vec j #f)) i))) It could probably be squeezed into a oneliner in python :)

Sean1708 9y ago
That sounds like a challenge (but I've goofed off work enough for one day so they'll have to be mediocre solutions): set(range(2, MAX_NUM)) - {j for i in range(2, MAX_NUM) for j in range(2*i, MAX_NUM, i)} Or to put it in the same form as the original: [False, False] + [k not in {j for i in range(2, MAX_NUM) for j in range(2*i, MAX_NUM, i)} for k in range(2, MAX_NUM)]
RodgerTheGreat 9y ago
If the goal is conciseness, let's use K. Start with a range: 1+!20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Prepend runs of 0 of each length with 1: (1,&:)'1+!20 (1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) Cycle each pattern to form a matrix: (20#1,&:)'1+!20 (1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) Sum the rows of the matrix: +/(20#1,&:)'1+!20 20 0 1 1 2 1 3 1 3 2 3 1 5 1 3 3 4 1 5 1 Find indices with exactly one factor: &1=+/(20#1,&:)'1+!20 2 3 5 7 11 13 17 19 Generalize to any upper limit x: {&1=+/(x#1,&:)'1+!x}100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 As an afterthought, I realized it's easier and equivalent to work from a 0-based range: {&2=+/(x#1,&:)'!x}100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 I couldn't precisely remember this function, but I'd seen the approach before and it was easy to build up piece by piece in the REPL.
bascule 9y ago
Have some Erlang: sieve(N) -> sieve(lists:seq(2, N), []). sieve([], L) -> lists:reverse(L); sieve([Prime|T], L) -> sieve([X || X <- T, X rem Prime /= 0], [Prime|L]).

by bjoli 9y ago

Sean1708 9y ago

That sounds like a challenge (but I've goofed off work enough for one day so they'll have to be mediocre solutions): set(range(2, MAX_NUM)) - {j for i in range(2, MAX_NUM) for j in range(2*i, MAX_NUM, i)} Or to put it in the same form as the original: [False, False] + [k not in {j for i in range(2, MAX_NUM) for j in range(2*i, MAX_NUM, i)} for k in range(2, MAX_NUM)]

RodgerTheGreat 9y ago

If the goal is conciseness, let's use K. Start with a range: 1+!20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Prepend runs of 0 of each length with 1: (1,&:)'1+!20 (1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) Cycle each pattern to form a matrix: (20#1,&:)'1+!20 (1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) Sum the rows of the matrix: +/(20#1,&:)'1+!20 20 0 1 1 2 1 3 1 3 2 3 1 5 1 3 3 4 1 5 1 Find indices with exactly one factor: &1=+/(20#1,&:)'1+!20 2 3 5 7 11 13 17 19 Generalize to any upper limit x: {&1=+/(x#1,&:)'1+!x}100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 As an afterthought, I realized it's easier and equivalent to work from a 0-based range: {&2=+/(x#1,&:)'!x}100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 I couldn't precisely remember this function, but I'd seen the approach before and it was easy to build up piece by piece in the REPL.

bascule 9y ago

Have some Erlang: sieve(N) -> sieve(lists:seq(2, N), []). sieve([], L) -> lists:reverse(L); sieve([Prime|T], L) -> sieve([X || X <- T, X rem Prime /= 0], [Prime|L]).