使用 for 循环，找到 1-100 之间的素数

Question

我尝试了很多方法来解决这个问题，但是...我找不到这段代码的问题所在。

我使用 Perl，我想找到 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";
    }
}

Answer 1

您在外层 for 循环的外部而不是内部初始化了 my $count=0;。

除此之外，$i 应该从 2 开始而不是 0。

Answer 2

在使用 Sieve of Eratosthenes. 时需要考虑一些事情，因为您在更高的范围内重用了 $count 中的值，所以它没有重置对于您要检查的每个数字。

但是，我稍微重新格式化了您的代码：

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;
}

您可以使用循环控制，而不是使用标志变量 ($count) 来确定要做什么。如果你找到任何除数，你就知道你找到了一个非素数，没有必要继续下去。也就是说，你不需要计算除数。

找到一个后，停下来继续下一个号码。为此，我标记了循环结构。这样，在内循环中我可以跳到外循环的下一次迭代。而且，通常，一旦我标记了一个循环，我就将它们全部标记，但你不需要这样做。

一旦你弄清楚了那部分，你就不需要做那么多工作了。除了 2，您知道所有偶数都不是质数。你不需要检查那些。所以，我不是聪明，而是把 2 作为一个特例来分解：

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;
}

内部循环也做了太多工作。 None 您要检查的数字中有偶数，因此您无需检查任何偶数除数（或选择 5 后以 5 结尾的那些）。而且，你只需要走到一半，所以当你到达数字的平方根时就可以停下来。

#!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;
}

最后，我将从命令行参数中获取最高的数字，但默认为 100。这样，外循环中的比较变为 <=:

#!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;
}

但是，ikegami 在评论中指出 for my $x (0..$n-1) 更为惯用。这不容易处理大于 1 的步长。您可以做各种事情来乘以该数字以获得候选数字，或者提前生成列表的方法（但这意味着您一次拥有所有列表）。我将改用 while，并假设这些其他位正常工作。

$get_number 是一些神奇的子程序，它总是返回下一个数字，而 is_prime 会做它所做的事情来做出决定：

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

这是一种可行的方法。首先，有一个漂亮的 Perl regex trick to determine primes。我使用它并不重要，因为你可以将它更改为任何你喜欢的，因为它隐藏在 is_prime 后面。这里最大的好处是它很短（有点炫耀）：

#!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+?)+\z/ }

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

generate_sub 有点棘手。首先，2 make 有点棘手。其次，Perl 没有像 Python 或 Ruby 这样的 yield （会很好）。为了解决这个问题，我将看到一个包含前两个数字的队列，然后根据最后一个数字添加下一个数字（因此，将 2 加到 3 得到 5，依此类推）。这会绕过从 2 到 3 的唯一间隔。如果队列中的下一个数字高于您想要的数字，这将停止。

但是，这有点复杂，只能处理 2 的特殊情况。我最近一直在玩一个不同的成语，虽然我不相信它是可取的。

state 是一种声明持久词法变量的方法。它运行仅在第一次执行时出现。我们将立即使用 state 到 return 第一个 2。然后，下次我们再来时，那个 $rc 语句没有运行而 $next 有 3。从那里，我得到当前数字（0+$next 所以它不是相同的数据），并在列表中递增 $next，但只有 return 该列表中的第一个。这只是一个压缩 if-else:

的技巧

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

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

我不建议您将此方法用于您的问题，但您应该考虑一种生成数字列表的方法，这样它就不会与问题紧密耦合。这样，您就可以摆脱循环结构。

但是，这比您需要知道的要多得多。

使用 for 循环，找到 1-100 之间的素数

using for loop, finding prime number between 1-100

perl