Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Re (tilly) 1: (Golf): Sieve of Eratosthenes

by tilly (Archbishop)
on May 19, 2001 at 23:08 UTC ( #81755=note: print w/ replies, xml ) Need Help??


in reply to (Golf): Sieve of Eratosthenes

Well both of my solutions have been beaten so I am willing to post them. But there are still a couple of hours for people to try to beat the current entries. But right now I am in a quandry about who is leading in the first. The best solution so far is 47 characters. It is basically MeowChow's solution with a trivial fix from chipmunk. I feel that it is "really" MeowChow's, but technically it was chipmunk who posted it. I will have to decide what to do with that one. For the bonus round tye is clearly leading.

What I did differently than everyone else is I used a hash. My idea was to use a hash and then mark off entries by assigning to a hash reference. If you assign a range of numbers starting with an odd, the odds conveniently become the keys. This unfortunately makes 2 a special case. For the general problem I snuck 2 past like this in 60 characters:

sub p{ %p=@_=3..1+pop;@p{2,map$f*$_,@_}=$f=$_ for@_;grep$p{$_},2,@_ }
For the second problem I just dropped the special logic for 2 and stuck it at the beginning of the list with this 61 character solution:
sub p{ 2,grep{$f=$_,@p{map$f*$_,3..$_[0]/$f}=0if$p{$_}}%p=3..1+$_[0] }
The observant will notice that this is indeed startlingly similar to tye's solution. If he tried to reverse-engineer mine, the copy is better than the original! (Possibly because he did not have my blind spot for using a hash...)


Comment on Re (tilly) 1: (Golf): Sieve of Eratosthenes
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://81755]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (9)
As of 2015-07-03 17:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (54 votes), past polls