Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

Re: (Golf): Sieve of Eratosthenes

by chipmunk (Parson)
on May 19, 2001 at 19:59 UTC ( #81731=note: print w/replies, xml ) Need Help??

in reply to (Golf): Sieve of Eratosthenes

This solution is very similar to japhy's, although I started it without looking at his. I did use his solutions to inspire me to shorten mine, though!

57 characters:

sub sieve { my@p;@_=2..pop;{push@p,$p=shift;redo if@_=grep$_%$p,@_}@p }
58 characters, strict-compliant:
sub sieve { my@p;@_=2..pop;{push@p,shift;redo if@_=grep$_%$p[-1],@_}@p }
BTW, what is the Big-O of the Sieve of Eratosthenes? :)

Replies are listed 'Best First'.
Re (tilly) 2: (Golf): Sieve of Eratosthenes
by tilly (Archbishop) on May 19, 2001 at 21:20 UTC
    The sieve of Eratosthenes is O(n*log(log(n))) arithmetic operations. Arithmetic operations themselves scale logarithmically officially there is another log operation in there. So within memory limits it should look basically linear in n. I might be willing to bend a log factor here or there. But if it isn't roughly linear in my tests, you don't qualify.

    And BTW I am not worrying about strict.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://81731]
[karlgoethebier]: is about to reach nirvana tonight...
[Lady_Aleena]: It could have meant a "Miserably Cute Event" or "Man Crush Everyday". 8)
[Corion]: choroba: Re the one-shot thing, I also thought of bit vectors and/or indexes into one common array from the hashes, but that makes maintenance of all these indices a chorse
[Corion]: *core
[Corion]: ** chore
[Corion]: So I guess I will simply implement the linear scan first and wait with more fancy stuff until it becomes a problem
[karlgoethebier]: Lady_Aleena: ++ for "The Man Crusher Everyday"
[karlgoethebier]: this mad my day
[karlgoethebier]: no typo
[marioroy]: At the Fransiscan monastery, got stuck up high in a tree from pruning and the chainsaw with large branch fell and broke the latter, but not me fortunately. Was stuck there for a while until a firetruck came by.

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (13)
As of 2017-05-29 08:30 GMT
Find Nodes?
    Voting Booth?