素因数分解

Twitterで素数がどうのこうのというのを見かけたので書いてみた。

元々のは素数計算（素数の生成？）のようでしたが、見た時に頭に浮かんだのは素因数分解だったので・・・。書いてる途中で気付きましたが、まあ・・・。

factor.pl

#!perl
use strict;
use warnings;

my $input = $ARGV[0] or die 'no input error.';
if($input =~ /^\d+$/) {
    print " $input = (1)";
    print " * $_" for &factor($input);
}
exit;

sub factor {
    my $value = shift or return;
    my @plist;
    my $f; $f = sub {
        my $p = shift;
        while($value % $p == 0) {
            push(@plist, $p);
            $value /= $p;
        }
    };
    $f->(2);
    for(my $i = 3; $i <= $value; $i += 2) {
        $f->($i);
    }
    return @plist;
}

こんな感じで。

大きい素数を持つ数字を扱うとかなり処理に時間がかかります。

素数の性質って、２以外は奇数、ということくらいしか思いつかなかったので・・・。

※ちなみに素因数分解する数字の1/2までの素数を予め持ってるっつーのが効率良いのかな。

最初、再帰的に処理するのかな〜。とか思い浮かべながら書いてたんですけど必要無かったですね。

まっ関数内関数を書いてみたかったんですけどね。んー、どういう場面で使えばいいのかは掴めてませんが・・・。

とりあえず、これくらいのならば１０分前後で書けるようになったかな。

prime.pl

#!perl
use strict;
use warnings;

my $input = $ARGV[0] or die 'no input error.';
my $continue = $ARGV[1];
if($input =~ /^\d+$/) {
    print " prime:\n";
    print "\t> $_\n" for &prime($input, $continue);
}
exit;

sub prime {
    my $value = shift or return;
    my $start = shift;
    unless($start) { $start = 2; }
    my @plist;
    my $f; $f = sub {
        my $p = shift or return;
        for(my $i = 2; $i <= $p / 2; $i++) {
            if($p % $i == 0) { return; }
        }
        return 1;
    };
    for(my $p = $start; scalar(@plist) < $value; $p++) {
        if($f->($p)) { push(@plist, $p); }
    }
    return @plist;
}

ちろっと改変して、素数を算出するスクリプトにしてみました。引数個数分の素数を算出します。
Ｃスタイルのfor文使いまくりですが、好きなのでしかたありません。。。

基本的な部分は変わって無いので重いです。。。