Sieve of Eratosthenes: Difference between revisions
Content deleted Content added
m renamed variables to be more consistent (n for non-primes, p for primes) |
→{{header|Lambdatalk}}: adding a recursive and iterative versions |
||
Line 11,279: | Line 11,279: | ||
=={{header|Lambdatalk}}== |
=={{header|Lambdatalk}}== |
||
<syntaxhighlight lang="scheme"> |
<syntaxhighlight lang="scheme"> |
||
1) recursive version {rsieve n} |
|||
⚫ | |||
{def rsieve |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
{def |
{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.r |
|||
{lambda {:a :i} |
|||
{if {< :i {A.length :a}} |
|||
then {if {= {A.get :i :a} 1} then :i else .} |
|||
⚫ | |||
else}}} |
|||
{lambda {:a} |
|||
{rsieve.disp.r :a 0}}} |
|||
{def rsieve.mark |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
{def rsieve.loop |
|||
{lambda {:a :n :i} |
{lambda {:a :n :i} |
||
{if {< :i {sqrt :n}} |
{if {< :i {sqrt :n}} |
||
then { |
then {rsieve.loop {if {= {A.get :i :a} 1} |
||
then { |
then {rsieve.mark :a :n :i {* :i :i}} |
||
else :a} |
else :a} |
||
:n {+ :i 1}} |
:n {+ :i 1}} |
||
else :a}}} |
else :a}}} |
||
{lambda {:n} |
|||
⚫ | |||
{ |
{rsieve.disp |
||
{rsieve.loop |
|||
{S.replace \s by space in |
|||
{ |
{rsieve.init :n} :n 2}}}} |
||
-> rsieve |
|||
⚫ | |||
{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.init |
|||
{lambda {: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} |
{lambda {:n} |
||
{ |
{isieve.disp |
||
{S.last |
|||
⚫ | |||
{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 |
|||
{ |
{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> |
</syntaxhighlight> |
||