Problem 3
素因数の最大値を求める問題。問題の数値が大きいからそれなりに時間がかかりますね。
なんでかは知らないけど、素因数は目的の数の二乗根より小さいのでそれで計算時間を短縮。
#!/usr/bin/perl use strict; use warnings; print "max prime factor is ", p3(600851475143), "\n"; # 6857 sub p3 { my ($num) = @_; my $max_prime_factor = 1; my $limit = sqrt($num); while(1){ if($num % 2 == 0){ $max_prime_factor = 2; $num /= 2; } else{ last; } } for(my $i = 3; $i <= $limit;){ if($num % $i == 0){ $max_prime_factor = $i; $num /= $i; } else{ $i += 2; } } $max_prime_factor = $num if $max_prime_factor == 1; return $max_prime_factor; }