How can I make my prime number generator better?

Discussion in 'Perl Misc' started by nikolas.britton@gmail.com, Mar 23, 2007.

  1. Guest

    How can I improve my code?... faster, better style, proper programming
    techniques, better algorithm? Thanks!

    #!/usr/bin/perl
    use strict;
    use warnings;
    use diagnostics;

    my $n = 100000; #limit at 6 * 10^14, regex's break.
    my $k = 6; #6 * 10^14, min value is 6.
    $k = int(($k / 6) + .5);
    my $y1; my $y2;

    for (1 .. int(($n * .1665) + .5)) {

    #check 6k - 1:
    $y1 = ((6 * $k) - 1);
    if ($y1 !~ m/5$/o) {
    for (1 .. (int((sqrt($y1) * .1665) + .5))) {
    $y2 = ((6 * $_) - 1);
    goto end1 if (($y1 / $y2) !~ m/\./o);
    $y2 += 2;
    goto end1 if (($y1 / $y2) !~ m/\./o);
    }
    #is prime tap 1:
    print "$y1\n";
    } end1:

    #check 6k + 1:
    $y1 += 2;
    if ($y1 !~ m/5$/o) {
    for (1 .. (int((sqrt($y1) * .1665) + .5))) {
    $y2 = ((6 * $_) - 1);
    goto end2 if (($y1 / $y2) !~ m/\./o);
    $y2 += 2;
    goto end2 if (($y1 / $y2) !~ m/\./o);
    }
    #is prime tap 2:
    print "$y1\n";
    } end2:

    $k++;
    }
    , Mar 23, 2007
    #1
    1. Advertising

  2. Klaus Guest

    On Mar 23, 1:47 am, wrote:
    > How can I improve my code?... faster, better style, proper programming
    > techniques, better algorithm? Thanks!


    As far as the goto's are concerned:

    perldoc perlsyn (section "Goto") :
    ++ In almost all cases like this, it's usually a far, far better idea
    ++ to use the structured control flow mechanisms of next, last,
    ++ or redo instead of resorting to a goto. For certain
    ++ applications, the catch and throw pair of eval{} and die()
    ++ for exception processing can also be a prudent approach.

    I would suggest to wrap an additional { ... } block around the "if
    ($y1 !~ m/5$/o) { ... }" statement. The additional block will be
    labled "end1:", and the "goto" will be replaced by "last".

    [ snip ]

    > $y1 = ((6 * $k) - 1);


    end1: { # additional block labeled end1:

    > if ($y1 !~ m/5$/o) {
    > for (1 .. (int((sqrt($y1) * .1665) + .5))) {
    > $y2 = ((6 * $_) - 1);
    > goto end1 if (($y1 / $y2) !~ m/\./o);

    last end1 if (($y1 / $y2) !~ m/\./o);

    > $y2 += 2;
    > goto end1 if (($y1 / $y2) !~ m/\./o);

    last end1 if (($y1 / $y2) !~ m/\./o);

    > }
    > #is prime tap 1:
    > print "$y1\n";

    } # remove the old label end1 here
    } # close the additional block

    There is also a test "if (($y1 / $y2) !~ m/\./o);"

    The "/o" regexp-modifier is only useful if there is an interpolated
    variable inside the regexp (which is not the case here), so the "/o"
    could be removed from the regexp.
    But I would suggest to get rid of the regexp alltogether and replace
    it by a simple "if ($y1 % $y2 == 0);"

    --
    Klaus
    Klaus, Mar 23, 2007
    #2
    1. Advertising

  3. Guest

    On Mar 22, 8:24 pm, "Klaus" <> wrote:
    > On Mar 23, 1:47 am, wrote:
    >
    > > How can I improve my code?... faster, better style, proper programming
    > > techniques, better algorithm? Thanks!

    >
    > As far as the goto's are concerned:
    >
    > perldoc perlsyn (section "Goto") :
    > ++ In almost all cases like this, it's usually a far, far better idea
    > ++ to use the structured control flow mechanisms of next, last,
    > ++ or redo instead of resorting to a goto. For certain
    > ++ applications, the catch and throw pair of eval{} and die()
    > ++ for exception processing can also be a prudent approach.
    >
    > I would suggest to wrap an additional { ... } block around the "if
    > ($y1 !~ m/5$/o) { ... }" statement. The additional block will be
    > labled "end1:", and the "goto" will be replaced by "last".
    >
    > [ snip ]
    >
    > > $y1 = ((6 * $k) - 1);

    >
    > end1: { # additional block labeled end1:
    >
    > > if ($y1 !~ m/5$/o) {
    > > for (1 .. (int((sqrt($y1) * .1665) + .5))) {
    > > $y2 = ((6 * $_) - 1);
    > > goto end1 if (($y1 / $y2) !~ m/\./o);

    >
    > last end1 if (($y1 / $y2) !~ m/\./o);
    >
    > > $y2 += 2;
    > > goto end1 if (($y1 / $y2) !~ m/\./o);

    >
    > last end1 if (($y1 / $y2) !~ m/\./o);
    >
    > > }
    > > #is prime tap 1:
    > > print "$y1\n";

    >
    > } # remove the old label end1 here
    > } # close the additional block
    >
    > There is also a test "if (($y1 / $y2) !~ m/\./o);"
    >
    > The "/o" regexp-modifier is only useful if there is an interpolated
    > variable inside the regexp (which is not the case here), so the "/o"
    > could be removed from the regexp.
    > But I would suggest to get rid of the regexp alltogether and replace
    > it by a simple "if ($y1 % $y2 == 0);"
    >


    Yes the modulus operation is much faster, benchmark says about 200%
    faster! Thanks!!! I would like to get rid of the goto's but I'm not
    sure what you wrote will work. I'm using them to break and to jump
    over the 'prime plucker' code. I've changed some of the comments and
    labels to help convey what it's doing:

    #!/usr/bin/perl
    use diagnostics;
    use warnings;
    use strict;

    my $n = 1000; #sets upper bound, max value is 10 ** 15.
    my $k = 6; #sets lower bound, min value is 6.
    $k = int($k / 6 + .5);
    my $y1; my $y2;

    for (1 .. int($n * .1665 + .5)) {

    #do 6k - 1:
    $y1 = (6 * $k - 1);
    if ($y1 !~ /5$/) { #separate wheat from chaff:
    for (1 .. int(sqrt($y1) * .1665 + .5)) {
    $y2 = (6 * $_ - 1);
    goto not_prime_1 if ($y1 % $y2 == 0);
    $y2 += 2;
    goto not_prime_1 if ($y1 % $y2 == 0);
    } #prime plucker 1:
    print "$y1 is prime.\n";
    } not_prime_1:

    #do 6k + 1:
    $y1 += 2;
    if ($y1 !~ /5$/) { #separate wheat from chaff:
    for (1 .. int(sqrt($y1) * .1665 + .5)) {
    $y2 = (6 * $_ - 1);
    goto not_prime_2 if ($y1 % $y2 == 0);
    $y2 += 2;
    goto not_prime_2 if ($y1 % $y2 == 0);
    } #prime plucker 2:
    print "$y1 is prime.\n";
    } not_prime_2:
    ++$k;
    }

    END
    Thanks for your help.
    , Mar 23, 2007
    #3
  4. Octo Guest

    On 23 Mar, 08:53, wrote:
    <snip>
    > Yes the modulus operation is much faster, benchmark says about 200%
    > faster! Thanks!!! I would like to get rid of the goto's but I'm not
    > sure what you wrote will work.

    <snip>

    I've amended your code to illustrate what was suggested:

    > #!/usr/bin/perl
    > use diagnostics;
    > use warnings;
    > use strict;
    >
    > my $n = 1000; #sets upper bound, max value is 10 ** 15.
    > my $k = 6; #sets lower bound, min value is 6.
    > $k = int($k / 6 + .5);
    > my $y1; my $y2;
    >
    > for (1 .. int($n * .1665 + .5)) {
    >
    > #do 6k - 1:
    > $y1 = (6 * $k - 1);

    P1: {
    > if ($y1 !~ /5$/) { #separate wheat from chaff:
    > for (1 .. int(sqrt($y1) * .1665 + .5)) {
    > $y2 = (6 * $_ - 1);
    > last P1 if ($y1 % $y2 == 0);

    ^^^^^^^
    > $y2 += 2;
    > last P1 if ($y1 % $y2 == 0);

    ^^^^^^^
    > } #prime plucker 1:
    > print "$y1 is prime.\n";
    > }

    }
    >
    > #do 6k + 1:
    > $y1 += 2;

    P2: {
    > if ($y1 !~ /5$/) { #separate wheat from chaff:
    > for (1 .. int(sqrt($y1) * .1665 + .5)) {
    > $y2 = (6 * $_ - 1);
    > last P2 if ($y1 % $y2 == 0);

    ^^^^^^^
    > $y2 += 2;
    > last P2 if ($y1 % $y2 == 0);

    ^^^^^^^
    > } #prime plucker 2:
    > print "$y1 is prime.\n";
    > }

    }
    > ++$k;
    >
    > }
    >
    > END
    > Thanks for your help.
    Octo, Mar 23, 2007
    #4
  5. Marc Espie Guest

    In article <>,
    <> wrote:
    >How can I improve my code?... faster, better style, proper programming
    >techniques, better algorithm? Thanks!


    Get rid of floating point arithmetic. Instead of time-consuming operation,
    like looping from 1 to sqrt(n), write a while loop that stops when
    i*i >= n.

    As far as algorithms go, look up `Erathosthene's sieve', probably on wikipedia.
    Marc Espie, Mar 23, 2007
    #5
  6. -berlin.de Guest

    Michele Dondi <> wrote in comp.lang.perl.misc:
    > On Fri, 23 Mar 2007 12:39:38 +0000 (UTC), (Marc Espie)
    > wrote:
    >
    > >Get rid of floating point arithmetic. Instead of time-consuming operation,
    > >like looping from 1 to sqrt(n), write a while loop that stops when
    > >i*i >= n.

    >
    > sqrt(n) can be precalculated, i*i must be calculated for every loop.


    Not necessarily. If the algorithm involves the calculation of n/i
    to determine divisibility, you can equivalently check for i >= n/i
    at no extra cost.

    Anno
    -berlin.de, Mar 23, 2007
    #6
  7. Marc Espie Guest

    In article <>,
    Michele Dondi <> wrote:
    >On Fri, 23 Mar 2007 12:39:38 +0000 (UTC), (Marc Espie)
    >wrote:
    >
    >>Get rid of floating point arithmetic. Instead of time-consuming operation,
    >>like looping from 1 to sqrt(n), write a while loop that stops when
    >>i*i >= n.

    >
    >sqrt(n) can be precalculated, i*i must be calculated for every loop.
    >

    Perl being interpreted, you can apply known optimizations to it,
    namely, (i+1)*(i+1) = i*i + 2*i + 1...
    Marc Espie, Mar 23, 2007
    #7
  8. -berlin.de Guest

    Abigail <> wrote in comp.lang.perl.misc:
    > () wrote on MMMMCMLII
    > September MCMXCIII in
    > <URL:news:>:
    > @@ How can I improve my code?... faster, better style, proper programming
    > @@ techniques, better algorithm? Thanks!
    >
    > A better algorith beats everything else.
    >
    > If you want to generate prime numbers starting from 1, sieves are your
    > best option. They have been your best option since antiquity.
    >
    > Here's an example of a sieve:
    >
    >
    > #!/opt/perl/bin/perl -l
    >
    > # A sieve based on base 6. Only possible primes are those numbers p
    > # for which p mod 6 == 1, or p mod 6 == 5.
    > #
    > # Let n = 6 * k + l (0 <= l < 6). Then the bit b associated with n is
    > # b = 2 * k + [undef, 0, undef, undef, undef, 1] -> [l]
    > # In reverse, given a bit b, the corresponding number n is
    > # n = 6 * int (b / 2) + [1, 5] -> [b % 2].


    [snip

    Ah, I remember that. You developed it from a modest beginning (base 10,
    if memory serves) to this form in steps, posting and discussing intermediate
    implementations on clpm. That was fun.

    Anno
    -berlin.de, Mar 23, 2007
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Joel Mayes

    Beginners prime number generator

    Joel Mayes, Dec 5, 2006, in forum: C Programming
    Replies:
    10
    Views:
    525
    Joel Mayes
    Dec 13, 2006
  2. John Posner

    Re: Infinite prime number generator

    John Posner, Jun 29, 2010, in forum: Python
    Replies:
    0
    Views:
    428
    John Posner
    Jun 29, 2010
  3. Jeremy Fischer
    Replies:
    0
    Views:
    184
    Jeremy Fischer
    Jan 16, 2005
  4. Chris Angelico

    Prime number generator

    Chris Angelico, Jul 10, 2013, in forum: Python
    Replies:
    11
    Views:
    159
  5. Joshua Landau

    Re: Prime number generator

    Joshua Landau, Jul 10, 2013, in forum: Python
    Replies:
    0
    Views:
    73
    Joshua Landau
    Jul 10, 2013
Loading...

Share This Page