0

I'd tried lots of ways to get rid of this problem but... I can't find what's the problem of this code.

I use Perl and I want to find the prime number between 1-100.

use strict;
my $i=0;
my $j=0;
my $count=0;
for ($i=0; $i<101; $i++)
{
    for ($j=2; $j<$i; $j++)
    {
        if ($i%$j==0)
        {
            $count+=1;
        }
    }
    if ($count==0)
    {
        print "$i\n";
    }
}    
2
  • 1
    Note that the clearer for my $x (0..$n-1) is preferred over for (my $x=0; $x<$n; ++$x)
    – ikegami
    Apr 4, 2021 at 18:01
  • 1
    You could maybe state what the problem is? See also How to Ask.
    – Robert
    Apr 4, 2021 at 19:45

2 Answers 2

4

There are a few things to think about as you use the Sieve of Eratosthenes. Armali already pointed out that you were reusing the value in $count because you had it in a higher scope, so it didn't reset for each number you wanted to check.

But, I reformatted your code a bit:

use v5.10;

NUM: for( my $i=1; $i < 101; $i++ ) {
    DIVISOR: for( my $j=2; $j < $i; $j++ ) {
        next NUM if $i%$j == 0;
    }
    say $i;
}

Instead of using a flag variable ($count) to figure out what to do, you can use loop controls. If you find any divisor, you know that you have found a non-prime and there's no need to continue. That is, you don't need to count divisors.

When you find one, stop and move on to the next number. To do that, I've labeled the looping constructs. That way, in the inner loop I can skip to the next iteration of the outer loop. And, usually, once I label one loop I label them all but you don't need to do that.

Once you figure that part out, you don't need to do so much work. Aside from 2, you know that all the even numbers are not prime. You don't need to check those. So, instead of being clever, I'll just break out 2 as a special case:

use v5.10;

say 2;

NUM: for( my $i = 3; $i < 101; $i += 2 ) {
    DIVISOR: for( my $j=2; $j < $i; $j++ ) {
        next NUM if $i%$j == 0;
    }
    say $i;
}

The inner loop is doing too much work too. None of the numbers that you are checking are even, so you don't need to check any even divisors (or those ending 5 once you choose 5). And, you only have to go half way, so you can stop when you get to the square root of the number.

#!perl
use v5.10;

say 2;

NUM: for( my $i = 3; $i < 101; $i += 2 ) {
    my $stop_at = int sqrt $i;
    DIVISOR: for( my $j=3; $j <= $stop_at; $j += 2 ) {
        next NUM if $i % $j == 0;
    }
    say $i;
}

And, for a final flourish, I'll take the top number from the command-line arguments but default to 100. With that, the comparison in the outer loop changes to <=:

#!perl
use v5.10;

my $limit = $ARGV[0] // 100;

say 2;
NUM: for( my $i = 3; $i <= $limit; $i += 2 ) {
    my $stop_at = int sqrt $i;
    DIVISOR: for( my $j=3; $j <= $stop_at; $j += 2 ) {
        next NUM if $i % $j == 0;
    }
    say $i;
}

But, ikegami notes in a comment that for my $x (0..$n-1) is more idiomatic. That doesn't easily handle step sizes larger than 1. You can do various things to multiply that number to get the candidate number, or ways to generate the list ahead of time (but that means you have the list all at once). I'll switch to a while instead, and assume that these other bits do their work properly.

The $get_number is some magic subroutine that always gives us back the next number, and the is_prime does what it does to make the determination:

while( my $n = $get_number->() ) {
    say $n if is_prime($n);
    }

Here's one way that might work. First, there's a nifty Perl regex trick to determine primes. It doesn't matter that I'm using that because you can change it to whatever you like because it's hidden behind is_prime. The biggest benefit here is that it's short (and a bit of a show off):

#!perl
use v5.10;

my $get_number = generate_sub( $ARGV[0] // 100 );

while( my $n = $get_number->() ) {
    say $n if is_prime($n);
    }

sub is_prime { ( '1' x $_[0] ) !~ /\A(11+?)\1+\z/ }

sub generate_sub {
    my( $limit ) = @_;
    sub {
        state $queue = [ 2, 3 ];
        return if $queue->[0] > $limit;
        push $queue->@*, $queue->[-1] + 2;
        shift $queue->@*;
        }
    }

The generate_sub is a bit more tricky. First, the 2 makes is a bit tricky. Second, Perl doesn't have a yield like Python or Ruby (would be nice). To get around that, I'll see a queue with the first two numbers then add the next number based on the last on (so, adding 2 to 3 gets 5, and so on). That gets around the unique interval from 2 to 3. This stops if the next number in the queue is above the one that you want.

But, that's a bit complicated and only there to handle the special case of 2. I've been playing with a different idiom lately although I'm not convinced its desirable.

The state is a way to declare a persistent lexical variable. It runs only on the first execution. We'll use a state to return the first 2 right away. Then, the next time we come around, that $rc statement doesn't run and $next has 3. From there, I get the current number (0+$next so it's not the same data), and increment $next in a list, but only return the first in that list. That's just a trick that condenses the if-else:

sub generate_sub {
    my( $limit ) = @_;
    sub {
        state $rc = do { return 2 };
        state $next = 3;

        return $next <= $limit ? ( 0+$next, $next += 2 )[0] : ();
        }
    }

I don't recommend this for your problem, but you should consider a way to generate the list of numbers so it's not tightly coupled to the problem. That way, you can get rid of the looping constructs.

But, that's much more than you needed to know.

4

You initialized my $count=0; outside instead of inside the outer for loop.

Besides that, $i should start from 2 rather than 0.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.