Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
I got the idea for this from Re: RE: sieve of Eratosthenes.

Here is the challenge.

Write a function p that takes one argument $n, and returns an array of all of the primes up to and including $n.

Now there is a very short answer to this problem using the infamous RE from Abigail, namely:

sub p{ grep{(1x$_)!~/^(11+)\1+$/}2..pop }
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:
  1. 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.
  2. 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 only strike out multiples of prime numbers.
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.

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.

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

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.

UPDATE
Minor clarifications on the wording.

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

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

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


In reply to (Golf): Sieve of Eratosthenes by tilly

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others examining the Monastery: (18)
    As of 2014-08-27 15:41 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      The best computer themed movie is:











      Results (242 votes), past polls