perl挑战二，有兴趣的同学赶紧来看看

只是一个红薯

定义一个半质数的概念：如果一个数恰好是两个质数的乘积（可以相同），则称它为半质数。前几个半质数是 4, 6, 9, 10, 14, 15, 21, 22, 25, 26。问题是，输入两个正整数x<=y，问[x,y]之间有多少个半质数？

输入,y

输出:[x,y]之间有多少个半质数。

输入数据范围 1<=x<=y<=2000000。
附上一种求质数的方法：

1. for my $t( $x..$y) {
   
2.     my $flag = 1;
   
3.     for (my $j = 2;$j <= sqrt($t);$j++) {
   
4.   # 如果可整除,则不是质数
   
5.     if ($t % $j == 0) {
   
6.         $flag = 0;
   
7.         last;
   
8.        }
   
9.     }
   
10. push @aa,$t if $flag;
    
11. }

复制代码

xiumu2280

默默去查了一下什么是质数···

只有1和它本身两个正因数的自然数，叫质数(Prime Number)。··

ly5066113

1. #! /usr/bin/perl
   
2. 
   
3. use strict;
   
4. use warnings;
   
5. 
   
6. my @pn;
   
7. my %pn;
   
8. my $x = 2;
   
9. my $y = 100;
   
10. my $c = 0;
    
11. 
    
12. for my $i ( $x .. $y )
    
13. {
    
14.         my $f = 1;
    
15.         for my $j ( 0 .. $#pn )
    
16.         {
    
17.                 last if $pn[$j] > sqrt($i);
    
18.                 if ( $i % $pn[$j] == 0 )
    
19.                 {
    
20.                         $f = 0;
    
21.                         $c ++ if exists $pn{$i/$pn[$j]};
    
22.                 }
    
23.         }
    
24.         if ( $f == 1 )
    
25.         {
    
26.                 push @pn, $i;
    
27.                 $pn{$i} = 1;
    
28.         }
    
29. }
    
30. 
    
31. print "$c\n";

复制代码

只是一个红薯

x,y非固定哦回复 3# ly5066113


   

ly5066113

回复 4# 只是一个红薯

1. $ cat test.pl
   
2. #! /usr/bin/perl
   
3. 
   
4. use strict;
   
5. use warnings;
   
6. 
   
7. my @pn;
   
8. my %pn;
   
9. my $x = shift;
   
10. my $y = shift;
    
11. my $c = 0;
    
12. 
    
13. for my $i ( 2 .. $y )
    
14. {
    
15.         my $f = 1;
    
16.         for my $j ( 0 .. $#pn )
    
17.         {
    
18.                 last if $pn[$j] > sqrt($i);
    
19.                 if ( $i % $pn[$j] == 0 )
    
20.                 {
    
21.                         $f = 0;
    
22.                         $c ++ if $i >= $x && exists $pn{$i/$pn[$j]};
    
23.                 }
    
24.         }
    
25.         if ( $f == 1 )
    
26.         {
    
27.                 push @pn, $i;
    
28.                 $pn{$i} = 1;
    
29.         }
    
30. }
    
31. 
    
32. print "$c\n";
    
33. $
    
34. $ ./test.pl 50 100
    
35. 17
    
36. $ ./test.pl 50 1000
    
37. 282

复制代码

pitonas

{:2_169:} 查一下下什么是质数

只是一个红薯

回复 5# ly5066113


   

rubyish

~

1. #!/usr/bin/perl
   
2. 
   
3. my ( $x, $y ) = do { print 'x, y: '; split /\s+/, <> };
   
4. my $count;
   
5. 
   
6. number: for my $i ( $x .. $y ) {
   
7.     my $yes = 0;
   
8.     loop: for ( 2 .. sqrt $i ) {
   
9.         next if $i % $_;
   
10.         $yes++ ? next number : ( $i /= $_ ) and goto loop;
    
11.     }
    
12.     $count++ if $yes == 1;
    
13. }
    
14. 
    
15. print $count;
    

复制代码

只是一个红薯

{:3_189:} 回复 8# rubyish


   

yestreenstars

代码有点丑，不过效率还是蛮高的：

1. my $x = shift;
   
2. my $y = shift;
   
3. my ( @array, $count );
   
4. loop: for my $i ( sqrt($x) .. $y/2 ) {
   
5.         next unless $i > 1;
   
6.         $i % $_ == 0 && next loop for 2 .. sqrt($i);
   
7.         push @array, $i;
   
8. }
   
9. for my $i ( 0 .. $#array ) {
   
10.         for my $j ( $i .. $#array ) {
    
11.                 if ( $array[$i] * $array[$j] >= $x && $array[$i] * $array[$j] <= $y ) {
    
12.                         $count++;
    
13.                 } else {
    
14.                         last;
    
15.                 }
    
16.         }
    
17. }
    
18. print "$count$/";

复制代码

效率对比，与@ly5066113和@rubyish的脚本做了下对比，a脚本是我的脚本，b脚本是ly5066113的，c脚本是rubyish的：

1. $ time ./a 2 1500000
   
2. 309289
   
3. 
   
4. real    0m9.516s
   
5. user    0m0.015s
   
6. sys     0m0.031s
   
7. 
   
8. $ time ./b 2 1500000
   
9. 309289
   
10. 
    
11. real    2m20.250s
    
12. user    0m0.015s
    
13. sys     0m0.031s
    
14. 
    
15. $ time ./c
    
16. 2 1500000
    
17. x, y: 309289
    
18. real    0m57.953s
    
19. user    0m0.015s
    
20. sys     0m0.062s

复制代码