3 ms·
I am sure that this is Perl. Let me build it up as it executes. First, pop returns the last element of an array. If no array is specified, @_ is used, which
by btilly 16y ago
I am sure that this is Perl. Let me build it up as it executes.
First, pop returns the last element of an array. If no array is specified, @_ is used, which is the default array into which function arguments are passed. Therefore pop gets at the last argument. If this function is called with one argument, it gets at the first argument.
sub sieve3 {
pop
}
Next .. is the range operator. It builds up a list from one number to another. In our case it will be building up a list of the possible numbers we will be searching for primes in.
sub sieve3 {
0..pop
}
As I mentioned before, @_ is the default array. Let's assign that list there so that it is available in a convenient way. To get at element $n (in Perl, '$' basically means 'the') you would write $_[$n]. If you have an array @things, you can create a slice with @_[@stuff].
sub sieve3 {
@_=0..pop
}
Next what grep does is run some piece of code for every element in a list and returns the values that were true. The list element is always aliased to $_. (Default things are named _, and as before, $ means the. So $_ is "the default thing.")
sub sieve3 {
grep{ ... test $_'s primality ... }@_=0..pop
}
We started with an array @_. The algorithm is that we'll go through that list, every time we encounter a prime we drop all of the multiples from the list and have a true value so we encounter it. Every time we encounter something that has been struck out we see that it has been struck out, and that test is false.
We will be striking out elements by assigning 0 or undef to them, this test for whether we're less than 2 eliminates 0, 1, and all previously struck out non-primes.
sub sieve3 {
grep{ ... filter out multiples of $_ ... if$_[$_]>1}@_=0..pop
}
We'll do the striking by assigning 0 to a list of multiples. This sets the first to 0 and the rest to undef.
sub sieve3 {
grep{@_[ ... multiples of $_ ... ]=0if$_[$_]>1}@_=0..pop
}
We need a list of all of the numbers from $_ to the number of elements over $_. Luckily @_ used in a calculation tells us the number of elements it has.
sub sieve3 {
grep{@_[... turn into list of multiples... $_..@_/$_]=0if$_[$_]>1}@_=0..pop
}
Unfortunately the code that we'll use to make the list of multiples will reuse the default variable $_, so we need to alias this $_ to a new variable, $a.
sub sieve3 {
grep{@_[ ... turn into list of multiples ... $_..@_/($a=$_)]=0if$_[$_]>1}@_=0..pop
}
And now we introduce map. Map is like grep, except that it transforms elements in place. The transformation here is that we want $a * $_. Note that there are 2 loops here, one from the grep and one from the map. $a is the variable from the grep, and $_ from the map.
sub sieve3 {
grep{@_[map$a*$_,$_..@_/($a=$_)]=0if$_[$_]>1}@_=0..pop
}
And now for the nastiest bit (you thought we were done??). Grep evaluates that slice in scalar context. In scalar context an array tells you the size of the array. The slice we're assigning to always has size at least 1 because we're assigning 0 to it, so whether or not the list of indexes is 0 we get a true value. (Don't worry if you didn't understand that, the upshot is that we're returning a true value when we see primes, so that grep will return them.)
And there is the entire Sieve of Eratosthenes. In surprisingly little Perl.
- StavrosK 16y agoHuh, it actually makes sense now, thank you.