more useful options PerlMonks

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

by japhy (Canon)
 on May 19, 2001 at 17:00 UTC ( #81707=note: print w/replies, xml ) Need Help??

in reply to (Golf): Sieve of Eratosthenes

Here is one of 68 characters in length:
```sub p{my@x;map{my\$c=\$_;\$_%\$c||++\$x[\$_]for@_}@_=2..pop;grep\$x[\$_]==1,0.
+.\$#x}
UPDATE: And another of 65:
```sub p{@_=2..pop;my\$c;while(\$_[\$c]){@_=(\$_[\$c],grep\$_%\$_[\$c],@_);\$c++}@
+_}
UPDATE: And another of 60:
```sub p{@_=2..pop;my\$c;@_=(\$_[\$c++],grep\$_%\$_[\$c-1],@_)while\$c<@_;@_}
UPDATE: And another of 40 (but I fear it strays from the rules...):
```sub p{grep{my\$c=\$_;\$#_==grep\$c%\$_,@_}@_=2..pop}

japhy -- Perl and Regex Hacker

Replies are listed 'Best First'.
Re (tilly) 1: (Golf): Sieve of Eratosthenes
by tilly (Archbishop) on May 19, 2001 at 18:40 UTC
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.

UPDATE
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.

Create A New User
Node Status?
node history
Node Type: note [id://81707]
help
Chatterbox?
 [LanX]: well try to find my profile xD [marto]: derp [marto]: I've never had an account, and wouldn't visit the site LanX having only a fake profile is hard if a flirt asks to befriend you [erix]: "surveillance companies" have been rebranded as "social media" [LanX]: I'm using whatapp though :-/ [LanX]: Snowden remins me of Evan Spiegel (... start of a new conspiracy theory) [LanX]: yes! The same person!

How do I use this? | Other CB clients
Other Users?
As of 2018-03-19 15:27 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (240 votes). Check out past polls.

Notices?