最小の積

Perl 30分プログラム

30分プログラム、その264。最小の積 via Project Euler - PukiWiki。

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり、そのような数字の中では最小の値である。
では、1 から 20 までの整数全てで割り切れる数字の中で最小の値はいくらになるか。

エラトステネスのふるいのように、先頭の数字で後続の数字を割りつつ、積を計算すればいいだろう、たぶん。詳しくはコードで:D。

使い方

$ perl product.pl
2520
232792560

ソースコード

#! /usr/bin/perl
# -*- mode:perl; coding:utf-8 -*-
#
# product.pl -
#
# Copyright(C) 2008 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2008/03/17 20:57:08
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#

use strict;
use warnings;

sub div($$){
    my ($x,$y) = @_;

    if($x % $y == 0){
	$x / $y;
    }else{
	$x;
    }
}

sub product($@){
    my ($n,$x,@xs) = @_;

    if(@xs){
	# 先頭の数字で後続の数字を割る
	#
	# e.g.
	#   2 3 4 5 6 -> 2 *3* 2 5 *3*
	#
	my @ys = map { div $_,$x } @xs;

	&product($n*$x,@ys);
    }else{
	$n*$x;
    }
}

print product(1,1..10),"\n";
print product(1,1..20),"\n";

参考