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

只是一个红薯

貌似loop只能算50之前的质数哦回复 10# yestreenstars


   

yestreenstars

回复 11# 只是一个红薯

我不明白你的意思～
   

rubyish

v2~

1. #!/usr/bin/perl
   
2. 
   
3. my ( $x, $y ) = do { print 'x, y: '; <> =~ /(\d+)/g };
   
4. # my ( $x, $y ) = ( 500, 1500000 );  # 309136
   
5. my ( $count, @prime, %prime );
   
6. 
   
7. number: for my $i ( 2 .. $y ) {
   
8.     my $prime = 1;
   
9.     my $sqrt  = sqrt $i;
   
10.     for (@prime) {
    
11.         last if $_ > $sqrt;
    
12.         next if $i % $_;
    
13.         $prime = 0;
    
14.         $i >= $x and $count++ if exists $prime{ $i / $_ };
    
15.         next number;
    
16.     }
    
17.     push @prime, $i and $prime{$i}++ if $prime;
    
18. }
    
19. print $count;

复制代码

rubyish

回复 10# yestreenstars

有点 small bug ?
my ( $x, $y ) = ( 100, 200 );
$count => 4    # 28
   

yestreenstars

@只是一个红薯@rubyish
多谢二位提醒，修正后的代码：

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

复制代码

效率和之前的一样~

rubyish

v3~
my ( $x, $y ) = ( 2, 1500000 );    # 1 秒

感谢 Eratosthenes, yestreenstars 2 位大牛的指点。

1. #!/usr/bin/perl
   
2. 
   
3. # my ( $x, $y ) = do { print 'x, y: '; <> =~ /(\d+)/g };
   
4. my ( $x, $y ) = ( 2, 1500000 );
   
5. my ( $y2, $sqrt, $count ) = ( $y / 2, sqrt $y );
   
6. my @prime = (1) x ( $y2 + 1 );
   
7. 
   
8. for my $i ( 2 .. sqrt $y2 ) {
   
9.     next unless $prime[$i];
   
10.     my $j = $i * $i;
    
11.     undef $prime[$j] or $j += $i while $j <= $y2;
    
12. }
    
13. 
    
14. @prime = grep $prime[$_], 2 .. $#prime;
    
15. 
    
16. for my $i ( 0 .. $#prime ) {
    
17.     last if $i > $sqrt;
    
18.     for my $j ( $i .. $#prime ) {
    
19.         my $sp = $prime[$i] * $prime[$j];
    
20.         $sp > $y ? last : $sp >= $x && $count++;
    
21.     }
    
22. }
    
23. 
    
24. print $count, $/;
    

复制代码