### Re: (Golf): Sieve of Eratosthenes

by Arguile (Hermit)
 on May 19, 2001 at 16:14 UTC ( #81706=note: print w/replies, xml ) Need Help??

in reply to (Golf): Sieve of Eratosthenes

Well, looking through tilly's previous golf entries I think I'll feel fine if length(\$my_code) <= 3*length(\$tilly_code).

sub c{(\$k,@_)=(\$#_)?@_:2..(\$n=@_[0]);@_=map{(\$_%\$k)?\$_:0}@_;push @_,\$k;\$k<=sqrt(\$n)?c(grep{!/^0/}@_):@_}
As for the lenght:
[arguile@cobalt ~]\$ wc -L sieve_golf 104 sieve_golf

True to the seive, it starts at k=2 eleminates n*k, then steps to next prime and repeats until k >= sqrt(n). Instead of mapping to 0 I would have loved to just drop them -- not bothering w/ the regexp for cleanup -- but I couldn't for the life of me figure out how.

The subroutine is recursive mainly b/c I had yet to try that technique and this seemed like a good time to try.

Sample output:

# display procedure blatantly stolen from Tye 2: 2 10: 2 3 5 7 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 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 169: 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

Thanks to Petruchio for his rewording of (\$k,@_)=(\$#_)?@_:2..(\$n=@_[0]) so I didn't produce an error. So far this seems like a great place to learn programming.</fawning>

#### Update

Scratched recursion and went w/ a conventional for loop, brought it down to 87 chars w/ strict compliance.

# non-strict sub c{\$n=pop;@_=2..\$n;for(\$k=2;\$k<=sqrt(\$n);(\$k)=@_){@_=grep!/^0/,(map +{(\$_%\$k)?\$_:0}@_),\$k}@_} # strict w/ less named vars sub c{pop;@_=2..\$_;for(my\$k=2;\$k<=sqrt;(\$k)=@_){@_=grep!/^0/,(map{\$_%\$ +k?\$_:0}@_),\$k}@_}

#### Update

No one else was mapping, and now I see why (75 chars).
sub e{pop;@_=2..\$_;for(my\$k=2;\$k<=sqrt;(\$k)=@_){@_=((grep\$_%\$k,@_),\$k) +;}@_}

Create A New User
Node Status?
node history
Node Type: note [id://81706]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (1)
As of 2018-04-22 03:30 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My travels bear the most uncanny semblance to ...

Results (82 votes). Check out past polls.

Notices?