Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses

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

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

in reply to Re: (Golf): Sieve of Eratosthenes
in thread (Golf): Sieve of Eratosthenes

I think I have to rule the 40 character solution out of bounds on the basis of the fact that you are walking through the numbers and testing whether each is prime. This loses the central idea of Eratosthenes which is that when you find a prime you immediately mark off its multiples.

Basically you reversed the role of the 2 loops.

The 60 character answer is impressive. However it seems to scale quadratically. I must confess that I don't see why it is scaling quadratically, but it clearly is. So unless you can explain why this is a bug in Perl, I am going to have to call this a solution to only the first problem.

I now understand why your 60 character solution is scaling slowly. It actually scales like O(n*n/log(n)), and it is because you are walking all of the primes with each strike rather than just the multiples of the current prime. So it definitely only is a solution to the first problem.

  • Comment on Re (tilly) 1: (Golf): Sieve of Eratosthenes

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://81718]
[choroba]: Unfortunately, none of it is online
[haukex]: I figured that POD tests make sense, but only as author tests
[choroba]: I mean, the slides are, but not the makefile with scripts to create them
[Corion]: haukex: I've only now arrived at that revelation ;)
[Corion]: choroba: I use spod5, which also has that support, and also implements its own kinda-make stuff
[haukex]: But that module I just linked to assumes that most verbatim blocks are runnable code, I have other modules where that's not the case, so there I just copy-and-paste the synopsis into the author tests...
[haukex]: not the most efficient, but then again, I don't have that many modules on CPAN :-)
[Corion]: haukex: Yes, but if it's only supposed to run on my machine, I can be far more liberal with how I extract the code etc.
[Corion]: haukex: Yes - I see the benefit of using Dist::Zilla for people with 150+ modules on CPAN, but I don't see it for myself, and I'm always put off from contributing to such modules because they require a lot of toolchain setup that I don't want to ...
[Corion]: ... spend time on if I only want to provide a short patch

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (11)
As of 2017-02-27 12:29 GMT
Find Nodes?
    Voting Booth?
    Before electricity was invented, what was the Electric Eel called?

    Results (385 votes). Check out past polls.