perlmeditation
tilly
Contest
Golf
I got the idea for this from [id://81667].<P>
Here is the challenge.<P>
Write a function p that takes one argument $n, and returns
an array of all of the primes up to and including $n.<P>
Now there is a very short answer to this problem using the
infamous RE from [Abigail], namely:
<code>
sub p{
grep{(1x$_)!~/^(11+)\1+$/}2..pop
}
</code>
Therefore I will add that the function must
be clearly based on the Sieve of Eratosthenes. The sieve
algorithm goes, "Form a list of integers. Knock out the
evens other than 2. Knock out the multiples of 3. Knock
out the multiples of 5. etc through the primes." For the
purposes of this golf I will allow the following relaxations
of the algorithm:
<ol>
<li> Any finite amount of special case logic is allowed as
long as your general test for non-divisibility by most
primes looks like the sieve.
<li> As long as the general pattern of the algorithm is
present, excess work is explicitly allowed. For instance
at the striking out stage, there is no need to <i>only</i>
strike out multiples of prime numbers.
</ol>
So basically if you form a list of possible numbers and
then go through rounds of elimination, then I will accept
that as a solution. But if, like the above RE solution,
you go through a series of numbers and then test each
number for primality, that will be rejected.<P>
To sweeten the bait, sometime later tomorrow I will post
my best solution. If anyone had come without 5 strokes of
that answer, the best entry gets a free PerlMonks t-shirt.
(The unlikely event of a tie will be resolved by whoever
got there first.) Entries that I can find a failing
boundary case for will not count.<P>
For bonus marks, and a second possible t-shirt, the same
problem but without the relaxation on the sieve. That is
in the elimination round you must only mark off multiples
of primes, and you cannot have sufficient wasted operations
to change the Big-O of the algorithm. (ie You can waste a
constant factor of overhead. But you cannot, for instance,
spend most of your running time marking off array elements
that are out of bounds.) However I will let you assume
that $n is above a fixed number. (I am not sure how people
will tackle this, but sometimes it is convenient to make a
special case out of 2.)<P>
A final note. Most mathematicians say that the first prime
is 2. However those who produce lists of primes like to
say 1. I don't care whether your sequence starts with 2
or 1, either is acceptable.<P>
<B>UPDATE</B><BR>
Minor clarifications on the wording.<P>
<B>UPDATE 2</B><BR>
[Masem] said I should state an approximate time when I will
post my solutions. I will make it whenever I get a chance
after 5PM EST. That may be well after because I am likely
to be off doing other things.<P>
<B>UPDATE 3</B><BR>
Golfing closed. My solutions got trashed. Now who won?
Well on technicalities you can argue [chipmunk] for the
main problem and [MeowChow] for the bonus. But I think
all will agree looking at the answers that the winning
ideas were [MeowChow] for the main problem and [tye] for
the bonus. I think the only fair answer is to declare
3 winners. [tye], [chipmunk] and [MeowChow] can contact
me with the desired size, color, and location to send
the shirts.<P>
And an honorable mention goes to [Arguile]. OK, so he
forgot to test whether [pop] populates $_ (it doesn't)
but if that is what he can do after 6 weeks of Perl, I
can only wonder what he will be like with a few more
months under his belt...