ぽち＊ろぐ

Perl で素因数分解

先日、ニコニコ生放送で C や Lua などのプログラミング言語を使ってプロジェクト・オイラーの問題を解くのを配信している初心者の方がいました。三問目で躓いて悩んでらっしゃったのを観て、うっかり触発されて、その問題を Perl で解いてみようかな？なんて気になってしまいました。

これは、600851475143 の素因数のうちの最大数を求める問題です。

下のコードは、600851475143 を小さい順に 2 から 600851475143 の平方根以下までの範囲の整数で割っていって、割り切れたら再帰的にまたその商を同じ手順でひたすらどんどん割り続け、最後に割り切れた商を最大の素因数として表示します。

#!/usr/bin/perl

use strict;
use warnings;

print &largest_prime_factor( 600851475143 ), "\n";

sub largest_prime_factor {
    my $n = shift;
    for ( my $i = 2; $i <= int sqrt $n; $i++ ) {
        return &largest_prime_factor( $n / $i ) if $n % $i == 0;
    }
    return $n;
}

その後、素因数分解のアルゴリズムを調べてみたら、もっとスマートな方法がたくさんあるようです。正規表現のパターンマッチを使って素因数分解しちゃうという、いかにも Perl ならではの方法まであったり…。