2009年5月20日星期三

[PerlChina] Re: 最简单的求素数算法

perl -MList::MoreUtils=all -le 'push @purl, 2; print 2; print for grep { my $c = $_; all { $c % $_ } @purl and push @purl, $c } 3..$ARGV[0]' 30

这是比较慢的版本,但是比较容易理解 :)

2009/5/20 purl lamp <lamp.purl@gmail.com>
分开来看比较容易,初始的数组是 0 .. 9:

$ perl -le 'print for @screen=(0,0,2..$ARGV[0])' 9
0
0
2
3
4
5
6
7
8
9

中间的 eval 从 2 到 9 的平方根循环,把其中所有的质数的倍数置零。
eval { my $p=$_; if ($screen[$p]) { $screen[$_ * $p]=0 for 2..$#screen/$p }} for 2..sqrt($#screen);

如果 $screen[$p] 不等于零则产生副作用:$screen[$_ * $p]=0 for 2..$#screen/$p

$ perl -le '@screen=(0,0,2..$ARGV[0]); eval { my $p=$_; if ($screen[$p]) { $screen[$_ * $p]=0 for 2..$#screen/$p }} for 2..sqrt($#screen); print for @screen' 9
0
0
2
3
0
5
0
7
0
0

然后用 grep 过滤掉非零。



2009/5/20 Michael Zeng <galaxy2004@gmail.com>

太牛了吧, 看不懂
 
记得 有本书 high order Perl 或者  algorithm with perl
 
这个找质数肯定 讲过的
 
 


 
2009/5/20 purl lamp <lamp.purl@gmail.com>
this one-liner is faster, run to 100000 in 0.5 seconds .


perl -e '@screen=(0,0,2..$ARGV[0]); map { my $p=$_; if ($screen[$p]) { $screen[$_ * $p]=0 for 2..$#screen/$p }} 2..sqrt($#screen); print qq($_\n) for grep {$_} @screen' $1


2009/5/20 Anthony WU <anthonywuy2k@gmail.com>
��不�是2及其倍�……

所以用 for (my $a=3;$a<100000;$a+=2) 最少能�少一半�行��

-------- Original Message  --------
Subject: [PerlChina] 最简单的求素数算法
From: 钟声 <gh00920307@163.com>
To: perlchina <perlchina@googlegroups.com>
Date: 20/5/2009 11:23

帮忙看下这是不是最简单的求素数算法
open TEXT,">value.txt";
@prime = (2..100000);
@list=();
while(my $a=shift @prime){
    push @list,$a;
    @prime = grep ($_%$a, @prime);
}
print TEXT (join " ",@list);
用了大概20多秒。。还有更快的吗
grip和map中第一个参数能不能用子进程呢




--
穿越地震带



穿越地震带 纪念汶川地震一周年



--  Best Regards, 	Anthony WU





--
           Yours Sincerely
                   Zeng Hong





--~--~---------~--~----~------------~-------~--~----~
您收到此信息是由于您订阅了 Google 论坛"PerlChina Mongers 讨论组"论坛。
 要在此论坛发帖,请发电子邮件到 perlchina@googlegroups.com
 要退订此论坛,请发邮件至 perlchina+unsubscribe@googlegroups.com
 更多选项,请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问该论坛

-~----------~----~----~----~------~----~------~--~---

没有评论: