Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hello iv been sitting with this broken code for hours now and cant fix it, so now im turning to you guys, pls help me figure out whats wron with my code 
my (@primes, $i);
for(@primes=(2), $i=3 ;scalar(@primes) < 1000 ;$i++)
{foreach my $p (@primes){
if ($i % $p == 0){
           $i++
}
    }
    push @primes, $i;
}

print ("@primes");

[download]
its a program that should list the first 1000 prime numbers, but it dsnt

Replies are listed 'Best First'.
Re: Prime list
by LanX (Saint) on Feb 08, 2015 at 22:05 UTC
    > been sitting with this broken code for hours now and cant fix it,

    no wonder it's unreadable... indentation rules man!

    get perltidy or at least a decent editor!

    update

    I was bored, here your homework:

    your basic problem is that you have to skip to the next iteration in the outer loop, thats what next LABEL does!

    ( did some adjustments to readability).

    my @primes=();

OUTER:
for ( my $i=2; @primes < 100; $i++) {
    for my $p (@primes) {
        if ($i % $p == 0) {
            next OUTER;
        }
    }
    push @primes, $i;
}
print "@primes";

    [download]

    Cheers Rolf

    PS: Je suis Charlie!

[reply]
[d/l]

      And, of course, the classic regex approach: 

      c:\@Work\Perl\monks>perl -wMstrict -le
"my @primes;
 ;;
 for (my $i = 2;  @primes < 10;  ++$i) {
   push @primes, $i if ('x' x $i) !~ m{ \A (..+) \1+ \z }xms;
   }
 ;;
 print qq{@primes};
"
2 3 5 7 11 13 17 19 23 29

      [download]

      Give a man a fish:  <%-(-(-(-<

[reply]
[d/l]
[select]
        Maybe a nice educational example to explain, how \1 backreference and backtracking in regex work... not so much for primes though.

        Homework wise I mean! ;-)

        Cheers Rolf

        PS: Je suis Charlie!

[reply]
        I love this one. Thanks for throwing it up again.

        -QM
        --
        Quantum Mechanics: The dreams stuff is made of

[reply]
Re: Prime list
by kroach (Pilgrim) on Feb 08, 2015 at 22:24 UTC

    Let's look at your first wrong result: 16

    $i starts at 14 and is compared against all already found prime numbers:

    • 14 % 2 == 0, so $i is now 15,
    • 15 % 3 == 0, so $i is now 16,
    • 16 % (5, 7, 11, 13) != 0

    the foreach loop ends and 16 is considered prime. 16 is not compared with 2 and 3 and because of that it's divisibility by 2 is not determined.

    The problem is you're unconditionally pushing to the @primes array. Whenever the $i % $p == 0 condition is met, processing of the current $i should end, since it's non-prime. Then the next number should be compared with ALL the currently found primes.

[reply]
Re: Prime list
by Discipulus (Canon) on Feb 09, 2015 at 08:29 UTC
    Hello,
    when i was writing Tk Tartaglia's triangle fun - Pascal's triangle fun i needed to check for primality and i found this thread with this fast solution; maybe you learn something from it

    HtH
    L*
    There are no rules, there are no thumbs..
    Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.
[reply]
[d/l]

      I would suggest actually looking at a sieve, for example the ones on RosettaCode. They are much faster than the trial division method you link to, albeit generating primes starting at two.

      For doing trial division, the skip-2-3 primality test from RosettaCode is twice as fast as the code you link to. Just wrap in something like: my @primes = grep { isprime($_) }  1..1000000;

      While the regex solution mentioned in another reply is super clever, it is also super not useful for the task once past toy sizes.

[reply]
[d/l]

Back to Seekers of Perl Wisdom