Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

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? :)


Comment on Re: (Golf): Sieve of Eratosthenes
Select or Download Code
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?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (6)
As of 2015-07-04 17:04 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 (60 votes), past polls