需要帮助了解Perl代码实现埃拉托色尼

的筛我发现用Perl编写的关于埃拉托色尼的筛（一种算法来找到号码给定范围内的素数），下面的代码和它的工作很好，但我不明白它。有人可以为我评论它吗，所以我会更好地了解如何找到质数？需要帮助了解Perl代码实现埃拉托色尼

$max= 120; 
@primes=(); 
@tested= (1); 
$j= 1; 
while ($j < $max) { 
    next if $tested[$j++]; 
    push @primes, $j; 
    for ($k= $j; $k <= $max; $k+=$j) { 
     $tested[$k-1]= 1; 
    } 
} 
print "@primes\n";

来源

2014-05-12 ec-m

一个关键的一点是，该算法很好地工作时'@ tested'被初始化为空数组或0代替1。即初始化，换句话说，一个红鲱鱼。它也奇怪地使用'$ tested [$ N] == 1'来记录'$ N + 1'已被测试的事实。 –

$max= 120; 
@primes=();

$tested可能是更好的名字类似$nonprime。虽然我们把1在数组中开始，它实际上并没有做什么有用的东西......它同样为空。

而且，@tested不是非质数的列表，但布尔值其索引的非质数的列表。如果由于某种原因，你想标记2作为非黄金，你必须做这样的事情，而不是：通过从1所有的整数@tested = (1,1);

@tested= (1); 
$j= 1;

扫描到120

while ($j < $max) {

如果我们已经检查这个数字素性和失败，重启循环来检查下一个号码。

next if $tested[$j++];

我们现在知道，j是一个最好的，因为我们还没有将其标记为不贷，所以我们可以把它添加到我们的列表的末尾。因此，最终名单将按升序排列。

push @primes, $j;

扫描该数组和末尾数组之间的每个剩余数字。我们每次递增通过我们新的质数，所以我们基本上跨过$j

for ($k= $j; $k <= $max; $k+=$j) {

马克每个多的所有倍数为测试。我们知道它不能是素数，因为它有$j作为一个因素。

 $tested[$k-1]= 1; 
    } 
}

该脚本的其余部分留给读者作为练习。实现

print "@primes\n";

来源

2014-05-12 19:47:47 Rook

'@ tested'的初始化并不重要...尝试删除它，或将1更改为0. –

@JonathanLeffler是的，只是发现了一个;） – Rook

我会重写（清理）如下脚本，使其更加清晰。

以此为教训，如果一个给变量有意义的名称，代码可以成为自我记录：

use strict; 
use warnings; 

my $max = 120; 
my @primes; 
my @notprime; 

for my $num (2..$max) { 
    next if $notprime[$num]; 
    push @primes, $num; 
    for (my $multiple = 2 * $num; $multiple <= $max; $multiple += $num) { 
     $notprime[$multiple] = 1; 
    } 
} 
print "@primes\n";

上Sieve of Eratosthenes维基百科的文章是要充分说明算法，并提供漂亮的小的视觉效果处理。然而，总结仅仅是这样的：

迭代所有整数从2到最大。
如果整数没有被标记为notprime，那么它的黄金！
然后，只需通过公认的首要的倍数周期，使我们可以将其标记为不是素数。

来源

2014-05-12 19:46:18 Miller

需要帮助了解Perl代码实现埃拉托色尼

回答

相关问题