素因数分解

Perl 30分プログラム

30分プログラム、その590。素因数分解をしてみる。
うわさによると、素因数分解をしてくれるUnixコマンドがあるらしいですよ。たしかfactorとかいう名前だったはずです。
教えてくれた人は、「ボクは必ずこれをインストールしとくんだ。2年に一度ぐらいの頻度で必要になるから」という分かるような分からないようなことをおっしゃってました。
というわけで、そんな重要なコマンドfactorを作ってみよう。

使い方

$ perl fact.pl 42
42 = 2 * 3 * 7

ソースコード

#! /usr/bin/perl
# -*- mode:perl; coding:utf-8 -*-
#
# fact.pl -
#
# Copyright(C) 2009 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2009/05/14 21:06:52
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#

use strict;
use warnings;

sub sieve(@){
    my (@xs) = @_;
    if (@xs) {
	my ($hd,@tl) = @xs;
	($hd,&sieve(grep { $_ % $hd != 0} @tl));
    } else {
	();
    }
}

sub primes($){
    my ($n) = @_;
    sieve(2..$n);
}

sub prime_factor($){
    my ($n) = @_;

    my @primes = primes($n);
    grep { $n % $_ == 0 } @primes;
}
foreach my $n (@ARGV) {
    print $n," = ",join(' * ', prime_factor($n)), "\n";
}

参考