Problem 12

12問目。三角数を求めて行ってその約数の個数が 501個を越える初めの数は何かという
問題。普通に約数を数えていくと時間がかかりすぎるので、wikipediaに書いていた約数の
個数を求める公式を利用。 nが x^a * y^bと素因数分解されるとき nの約数の個数は
(a+1)(b+1)となるらしいので、それを利用。普通に求めると数分かかっても解けないものが
20秒ほどで解けました。素数の場合は結局最後まで求めてしまうから素数の判定を行ったら
多少早くなるのかもしれないけど、それはそれでオーバーヘッドがありそうなので実際は
どうなるんだろう？要検討。

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

my ($num, $triangle_num) = p12(501);
print "answer is ${num}th $triangle_num \n"; # answer is 12375th 76576500 

sub p12
{
  my ($num) = @_;
  my $i = 1;
  while(1){
    my $triangle_num = get_triangle_number($i);
    return ($i, $triangle_num) if get_divisor_count($triangle_num) >= $num;
    $i++;
  }
}

sub get_divisor_count
{
  my ($num) = @_;
  my %divisor;

  while(1){
    last if $num % 2 != 0;
    $num /= 2;
    $divisor{'2'}++;
  }

  my $limit = $num;
  for(my $i = 3; $i <= $limit;){
    if($num % $i == 0){
      $num /= $i;
      $divisor{$i}++;
      last if $num == 1;
    }
    else{
      $i += 2;
    }
  }

  my $divisor_count = 1;
  map {$divisor_count *= ($divisor{$_} + 1);}(keys %divisor);
  return $divisor_count;
}

sub get_triangle_number
{
  my ($num) = @_;
  my $sum = 0;

  map {$sum += $_;}(1..$num);
  return $sum;
}