Rosetta Code

Sieve of Eratosthenes: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Amarty (talk | contribs)
99 edits
Amarty (talk | contribs)
99 edits
Line 11,283:
{def rsieve
 
{def rsieve.initmark
{lambda {:an :na :i :kj}▼
{def rsieve.init.r
{lambdaif {< :nj :an}
{if then {<=rsieve.mark :n 0}
then {A.set! :j . :a}
else :a}i▼
else {rsieve.init.r {- :n 1} {A.addlast! 1 :a}}}}}
:n {+ :i 1:j}}▼
{lambda {:n}▼
{rsieve.init.r :n {A.new}else :a}}}
 
{def rsieve.disploop
▲ {lambda {:n :a :i}
{def rsieve.disp.r
{lambdaif {< {* :ai :i} :n}
{if {< :ithen {Arsieve.lengthloop :a}}n
then {if {=W.equal? {A.get :i :a} 1} then :i else .}
{rsieve.disp.r :a {+ :i 1}} then :a
then else {rsieve.mark :an :na :i {* :i :i}}}▼
else}}}▼
{+ :i 1}}
{lambda {:a}
{rsieve.disp.r else :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 {rsieve.loop {if {= {A.get :i :a} 1}
▲ then {rsieve.mark :a :n :i {* :i :i}}
▲ else :a}
▲ :n {+ :i 1}}
else :a}}}
 
{lambda {:n}
{S.replace \s by space in
{rsieve.disp▼
{S.replace (\[|\]|\.|,) by space in
{rsieve.loop
{rsieveA.init :n} :n 2}}}}disp
{A.slice 2 -1
▲ {def {rsieve.loop :n
{A.new {S.serie {*0 :i :in}} :n :i2}}}} }}}▼
-> rsieve
 
{sieversieve 5001000}
-> 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 419463 .467 421479 .487 .491 .499 .503 .509 .521 .523 .541 .547 431557 .563 433569 .571 .577 .587 .593 .599 439601 .607 .613 .617 443619 .631 .641 .643 .647 .653 449659 .661 .673 .677 .683 .691 .701 .709 457719 .727 .733 .739 461743 .751 463757 .761 .769 .773 467787 .797 .809 .811 .821 .823 .827 .829 .839 .853 .857 .859 479863 .877 .881 .883 .887 .907 .911 .919 487929 .937 .941 .947 491953 . . . . . . . 499967 971 977 //983 in991 40ms997
 
Note: onthis myversion computerdoesn't avoid stackoverflow for n > 750.
 
2) iterative version {isieve n}
Line 11,332 ⟶ 11,320:
{def isieve
 
{def isieve.initmark
{lambda {:n :a :i}
{A.new {S.map {{lambda {_}:a 0:j} {SA.serieset! 1:j . :n}} }}a}
▲ else} } :a}
 
{S.serie 0 {-* {A.length:i :ai} 1}:n :i} }}}▼
{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}
{S.replace \s by space in
{isieve.disp
{S.replace (\[|\]|\.|,) by space in
{S.last
▲ {rsieveA.disp
{S.map {{lambda {:n :a :i}
{if {= {A.getslice :i2 :a}-1 0}
then {isieveS.mark :n :alast :i}
{S.map {{lambda {:n :a :i} {if {W.equal? else{A.get :i :a} .}
} :n {isieve.init :n}} then
{S.serie 2 else {sqrtisieve.mark :n} 1}:a :i}}}}}
} :n {A.new {S.serie 0 :n}}}
-> isieve
{S.serie 2 {sqrt :n} 1}}}}}}}}}
▲{def-> isieve.disp
 
{isieve 5001000}
-> 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 419463 .467 421479 .487 .491 .499 .503 .509 .521 .523 .541 .547 431557 .563 433569 .571 .577 .587 .593 .599 439601 .607 .613 .617 443619 .631 .641 .643 .647 .653 449659 .661 .673 .677 .683 .691 .701 .709 457719 .727 .733 .739 461743 .751 463757 .761 .769 .773 467787 .797 .809 .811 .821 .823 .827 .829 .839 .853 .857 .859 479863 .877 .881 .883 .887 .907 .911 .919 487929 .937 .941 .947 491 . . . . . . . 499953 .967 971 977 //983 in991 15ms997
 
Notes:
Note: this version avoids the stackoverflow. From 1 to 1000000 there are 78500 primes (computed in 95000ms) and the last is 999983.▼
- this version avoids stackoverflow.
▲Note: this version avoids the stackoverflow.- From 1 to 1000000 there are 78500 primes (computed in 95000ms) and the last is 999983.
 
</syntaxhighlight>
Retrieved from "https://rosettacode.org/wiki/Sieve_of_Eratosthenes"