素因数絡みの問題が多いくて何度も書くのはめんどいのでモジュール化してみた。
(※のちのちメソッドをいろいろ追加する予定。)
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
