エラトステネスの篩

最近になってhttp://projecteuler.netの問題を少しずつ解き始めているのだけど
素因数絡みの問題が多いくて何度も書くのはめんどいのでモジュール化してみた。
(※のちのちメソッドをいろいろ追加する予定。)

package prime_factors;
use strict;
use warnings;

sub new{
  my $package = shift;
  my $ref = {};
  bless $ref, $package;
}

sub prime_factor{
  my $package = shift;
  my ($number) = @_;
  my $sqrt_num = int sqrt $number;
  my @prime_number = (2, 3, 5);
  my @prime_list;
  foreach (@prime_number){
    while($number % $_ == 0){
      $number /= $_;
      push @prime_list, $_;
    }
  }
  
  my $flag = my $flag7 = my $flag11 = 1;
  for(my $i=0; $flag; $i++){
    while ($number % (6*$i+7) == 0){
      $number /= 6 * $i + 7;
      push @prime_list, 6*$i+7;
    }
    while ($number % (6*$i+11) == 0){
      $number /= 6 * $i + 11;
      push @prime_list, 6*$i+11;
    }
    $flag7  = 0 if($sqrt_num<=(6*$i+7)  || $number == 1);
    $flag11 = 0 if($sqrt_num<=(6*$i+11) || $number == 1);
    $flag = 0 if(!$flag7 && !$flag11);
  }
  push @prime_list, $number if($number > 1);
  return @prime_list;
}
1;

で、確認の為使ってみる。(タイムも計測)

use strict;
use warnings;
use prime_factors;
use Time::HiRes qw(gettimeofday tv_interval);
my %time;
$time{'start'} = [gettimeofday];

my $obj = prime_factors -> new;

my $number = 600851475143;
my @list = $obj -> prime_factor(600851475143);
print "$numberの素因数は、@list\n";

$time{'end'} = [gettimeofday];
printf "time:%.3f second\n", tv_interval $time{'start'}, $time{'end'};
__END__

結果。


※測定に使ったノートPC。
OS:Microsoft Windows XP Professional Version2002 SP2
CPU:Intel® Core™2 Duo 2GHz
ﾒﾓﾘ:1GB RAM