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

Problem 5

euler perl


5問目。1から20までのすべての整数で割り切れる数の最小値を求めろ。
たぶん 1から20の最小公倍数を求めれば答えになるでしょう。リストからポップして
最小公倍数をどんどん求めていく。aとbの最小公倍数は a * b / (aとbの最大公約数)に
なるそうなので、そのまま実装。

#!/usr/bin/perl
use strict;
use warnings;

print "num is ", p5(20), "\n"; # 232792560

sub p5
{
  my ($limit) = @_;

  my @list = (1..$limit);
  my $num1 = shift @list;
  my $num2 = shift @list;
  my $num3 = saisyou($num1, $num2);

  while(@list){
    my $num4 = shift @list;

    $num3 = saisyou($num3, $num4);
  }

  return $num3;
}

sub saisyou
{
  my ($num1, $num2) = @_;
  return $num1 * $num2 / gcd($num1, $num2);
}

sub gcd
{
  my ($num1, $num2) = @_;

  if($num1 % $num2 == 0){
    return $num2;
  }
  else{
    gcd($num2, $num1 % $num2);
  }
}