Sieve of Eratosthenes: Difference between revisions

Line 11,279:

=={{header|Lambdatalk}}==

1) recursive version {rsieve n}

⚫

{def ~~sieve~~

{def ~~sieve.rec2~~

{def rsieve

⚫

{lambda {:a :n :i :k}

⚫

{if {< :k :n}

⚫

then {~~sieve~~.~~rec2~~ {A.set! :k 0 :a} :n :i {+ :k :i}}

⚫

else :a}}}

{def ~~sieve~~.~~rec1~~

{def rsieve.init

{def rsieve.init.r

{lambda {:n :a}

{if {<= :n 0}

then :a

else {rsieve.init.r {- :n 1} {A.addlast! 1 :a}}}}}

{lambda {:n}

{rsieve.init.r :n {A.new}}}}

⚫

{def rsieve.disp

{def rsieve.disp.r

{lambda {:a :i}

{if {< :i {A.length :a}}

then {if {= {A.get :i :a} 1} then :i else .}

⚫

{rsieve.disp.r :a {+ :i 1}}

else}}}

{lambda {:a}

{rsieve.disp.r :a 0}}}

{def rsieve.mark

⚫

{lambda {:a :n :i :k}

⚫

{if {< :k :n}

⚫

then {rsieve.mark {A.set! :k 0 :a} :n :i {+ :k :i}}

⚫

else :a}}}

{def rsieve.loop

{lambda {:a :n :i}

{if {< :i {sqrt :n}}

then {~~sieve~~.~~rec1~~ {if {= {A.get :i :a} 1}

then {rsieve.loop {if {= {A.get :i :a} 1}

then {~~sieve~~.~~rec2~~ :a :n :i {* :i :i}}

then {rsieve.mark :a :n :i {* :i :i}}

else :a}

:n {+ :i 1}}

else :a}}}

{lambda {:n}

⚫

{def ~~sieve~~.disp

{~~lambda {:s}~~

{rsieve.disp

{rsieve.loop

{S.replace \s by space in

{S.~~map~~ ~~{{lambda {~~:~~a :i~~} ~~{if {= {A.get~~ :i :a} 1} ~~then :i else~~}~~} :s~~}

{rsieve.init :n} :n 2}}}}

-> rsieve

⚫

{S.~~serie~~ 2 {~~- {A.length~~ :s} 1}}} ~~}}}~~

{sieve 500}

-> 0 1 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 . . . 101 . 103 . . . 107 . 109 . . . 113 . . . . . . . . . . . . . 127 . . . 131 . . . . . 137 . 139 . . . . . . . . . 149 . 151 . . . . . 157 . . . . . 163 . . . 167 . . . . . 173 . . . . . 179 . 181 . . . . . . . . . 191 . 193 . . . 197 . 199 . . . . . . . . . . . 211 . . . . . . . . . . . 223 . . . 227 . 229 . . . 233 . . . . . 239 . 241 . . . . . . . . . 251 . . . . . 257 . . . . . 263 . . . . . 269 . 271 . . . . . 277 . . . 281 . 283 . . . . . . . . . 293 . . . . . . . . . . . . . 307 . . . 311 . 313 . . . 317 . . . . . . . . . . . . . 331 . . . . . 337 . . . . . . . . . 347 . 349 . . . 353 . . . . . 359 . . . . . . . 367 . . . . . 373 . . . . . 379 . . . 383 . . . . . 389 . . . . . . . 397 . . . 401 . . . . . . . 409 . . . . . . . . . 419 . 421 . . . . . . . . . 431 . 433 . . . . . 439 . . . 443 . . . . . 449 . . . . . . . 457 . . . 461 . 463 . . . 467 . . . . . . . . . . . 479 . . . . . . . 487 . . . 491 . . . . . . . 499 // in 40ms

2) iterative version {isieve n}

⚫

{def isieve

{def isieve.init

{lambda {:n}

⚫

{A.new {S.map {lambda {_} 0} {S.serie 1 :n}} }}}

{def isieve.disp

{lambda {:a}

{S.map {{lambda {:a :i} {if {= {A.get :i :a} 0} then :i else .}} :a}

{S.serie 0 {- {A.length :a} 1}}}}}

{def isieve.mark

{lambda {:n :a :i}

{S.map {{lambda {:a :j} {A.set! :j 1 :a}} :a}

{S.serie {* :i :i} :n :i} }}}

{lambda {:n}

{~~sieve~~.disp

{isieve.disp

{S.last

⚫

~~{sieve.rec1~~ {A.new {S.map {lambda {_} 1} {S.serie 1 :n}}}

:n ~~2}}}}~~

{S.map {{lambda {:n :a :i}

{if {= {A.get :i :a} 0}

-> sieve

then {isieve.mark :n :a :i}

else}

} :n {isieve.init :n}}

{S.serie 2 {sqrt :n} 1} }}}}}

-> isieve

{~~sieve~~ ~~100~~}

{isieve 500}

-> 0 1 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 . . . 101 . 103 . . . 107 . 109 . . . 113 . . . . . . . . . . . . . 127 . . . 131 . . . . . 137 . 139 . . . . . . . . . 149 . 151 . . . . . 157 . . . . . 163 . . . 167 . . . . . 173 . . . . . 179 . 181 . . . . . . . . . 191 . 193 . . . 197 . 199 . . . . . . . . . . . 211 . . . . . . . . . . . 223 . . . 227 . 229 . . . 233 . . . . . 239 . 241 . . . . . . . . . 251 . . . . . 257 . . . . . 263 . . . . . 269 . 271 . . . . . 277 . . . 281 . 283 . . . . . . . . . 293 . . . . . . . . . . . . . 307 . . . 311 . 313 . . . 317 . . . . . . . . . . . . . 331 . . . . . 337 . . . . . . . . . 347 . 349 . . . 353 . . . . . 359 . . . . . . . 367 . . . . . 373 . . . . . 379 . . . 383 . . . . . 389 . . . . . . . 397 . . . 401 . . . . . . . 409 . . . . . . . . . 419 . 421 . . . . . . . . . 431 . 433 . . . . . 439 . . . 443 . . . . . 449 . . . . . . . 457 . . . 461 . 463 . . . 467 . . . . . . . . . . . 479 . . . . . . . 487 . . . 491 . . . . . . . 499 . // in 15ms

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

</syntaxhighlight>