読者です 読者をやめる 読者になる 読者になる

初代Masteries

きっとモヒカンにもなれないお前たちに告げる!!!

Project Euler - Problem 3

Problem 3

素因数分解.
いろいろ悩んだ結果, 王道というか, 素直に実装してみた感じです.

use strict;
use warnings;
use Math::BigInt;

my $n = Math::BigInt->new('600851475143');

print "$n:";

for (2..int($n->copy->bsqrt)) {
    while ($n->copy->bmod($_) == 0) {
        $n->bdiv($_);
        print " $_";
    }
    last if $n->copy->bcmp(1) == 0;
}

print "\n";

素因数分解する値が大きいので, Math::BigIntを使って実装しました.
copyとか多くて, 綺麗じゃないなあ...

というか, いちいちPerlでスクリプト書かなくてもfactorコマンドで事足りますねコレ.
速さも断然違いますし.

追記


@さんよりこのような意見を頂きました! というわけで書き換えドンッ!

use strict;
use warnings;
use bigint;

my $n = 600851475143;
my $max = int(sqrt($n));

print "$n:";

for (my $i = 2; $i <= $max; $i++) {
    while ($n % $i == 0) {
        $n = $n / $i;
        print " $i";
    }
    last if $n == 1;
}

print "\n";

use bigintを使うことで意識することなくMath::BigIntを利用することができます.
また, 先のコードだと最初に2からint(sqrt(600851475143))までのリストを作ってしまうので, C言語っぽいfor(これ以外のいい呼び方ってあるのかなあ... 3要素のforとか?)に書き直してみました.

Math::BigIntは知っていましたがbigintは知らなかったのでいい勉強になりました. @さん, どうもありがとうございました!

更に追記

...という事らしいので, C言語っぽいforにする必要はそんなにない... っぽい?

use strict;
use warnings;
use bigint;

my $n = 600851475143;
my $max = int(sqrt($n));

print "$n:";

for my $i (2..$max) {
    while ($n % $i == 0) {
        $n = $n / $i;
        print " $i";
    }
    last if $n == 1;
}

print "\n";

これでも普通に動きますね!