Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Re: Project Euler (a series of challenging mathematical/computer programming problems)

by GrandFather (Cardinal)
on Feb 04, 2006 at 08:50 UTC ( #527911=note: print w/ replies, xml ) Need Help??


in reply to Project Euler (a series of challenging mathematical/computer programming problems)

I notice that a lot of the problems involve prime numbers. Is there an efficient way of generating the first n prime numbers? I know how to sieve for primes in a up to some maximum value, but that doesn't give the first n. Hints?


DWIM is Perl's answer to Gödel


Comment on Re: Project Euler (a series of challenging mathematical/computer programming problems)
Re^2: Project Euler (a series of challenging mathematical/computer programming problems)
by BrowserUk (Pope) on Feb 04, 2006 at 09:16 UTC

    How many do you want? The first 1,000, first 10,000 and first 1 to 15 million.

    Download the list of your choice, reformat it to one/line and a fixed length (9 chars +newline covers the first 15 million), and you can grab as many as you need quickly and cheaply.

    my $wanted = 500; open my $primes, '<', 'primes.txt' or die $!; my @primes = split "\s+", do{ local $/=\($wanted * 10); <$primes> }; close $primes;

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

      Humph, that feels like cheating to me :).

      Thanks for the links, a solution to the problem though not a answer to the question.


      DWIM is Perl's answer to Gödel

        Okay. Since none of the math guys have answered, I'll risk telling you my uninformed opinion on the matter. As far as I am aware:

        1. The most efficient way of generating 'small' primes, defined as < 1e10, is the Sieve of Atkins, which is a kind of variation on the the Sieve of Eratosthenes that uses quadratic forms. I read that. I don't know what it means :)

          For this to be efficient for time requires it to be coded in platform specific C (with masses of performance critical bit twiddling), or hand crafted assembler that also requires intimite knowledge of the performance characteristics of the cpu used.

          There is also a method known as 'wheel factorisation', but again, you cannot predict how high you would need to go before you will find the N you want. It has the advantage of not requiring the retention of the list of primes so far, but requires more divsions and so is generally slower.

        2. As with the SoE, there is no exact method of knowing how high to go with the SoA in order to generate the first N primes.

          The best you can do is set your upper bound to N log N where N is the number you wish to find. This approximation apparently tends to get more accurate the higher you go?

        You could download a good implementation that will generate the list very quickly. Once you've generated the list once, the lookup method is probably quicker.

        You could maybe make it quicker still by storing the list in packed binary. You'd only need a 60 MB file instead of 160 MB, and would read less. unpacking to an array may be quicker than conversion from ascii.

        For my purposes a while back, I wanted the nearest prime less than a number within the program, so a binary chop lookup with a resonable guess at starting position worked best for me.


        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.

      No need to reformat, just use the script below to put the large primes file in a DBD::SQLite2 database. First, download and unzip the files that contain the first 15 million primes in chunks of 1 million. You will have primes1.txt through primes15.txt in a directory. Run this there:

      #!/bin/perl use strict; use warnings; use DBI; my $dbh = DBI->connect('dbi:SQLite2:dbname=primes.db','','',{RaiseErro +r=>1}); my $cnt = 0; # 'number' has to be text because of length $dbh->do('CREATE TABLE primes (id INTEGER, number TEXT)'); for (1..15) { $cnt = add_primes($dbh,$cnt,"primes$_.txt") } sub add_primes { my ($db, $c, $filename) = @_; open my $file, '<', $filename or die("Can't read '$filename': $!") +; print STDERR "Adding primes from $filename\n"; #first two lines are not data, skip them for (1..2) { <$file> } eval { $db->begin_work; my $sth = $db->prepare('INSERT INTO primes (id,number) VALUES +(?,?)'); while (<$file>) { foreach ( split(/\s+/,$_) ) { $sth->execute(++$cnt,$_) } } $db->commit; }; if ($@) { print STDERR "Died while processing prime #$cnt, with error:\n +$@"; exit; } return $cnt; }

      Then you can always ask for the n'th prime with the SQL (? is n)

      SELECT number FROM primes WHERE id = ?
      <-radiant.matrix->
      A collection of thoughts and links from the minds of geeks
      The Code that can be seen is not the true Code
      I haven't found a problem yet that can't be solved by a well-placed trebuchet

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://527911]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (8)
As of 2014-12-27 22:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (177 votes), past polls