Problem 21

10000までの友愛数の総和を求めろという問題。ものすごく単純な方法は即効でかけたけど
遅かったので、Wikipediaの約数の項目を参考に修正しました。そしたらいくらか早くなりました。
キャッシュの機能をつけたらもう少し早くなりそうな気がしますが、それは今回はなしで。

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

print "Answer is ", p21(10000), "\n";

sub p21 {
    my ($limit) = @_;
    my @amicables;
    my $amicable_number = 0;

    for my $i (2..$limit) {
        my $sum = get_prime_divisor(fact_prime($i)) - $i;
        $amicables[$i] = $sum;

        if (defined($amicables[$sum]) && $sum != $i) {
           $amicable_number += ($i + $sum) if $amicables[$sum] == $i;
        }
    }

    return $amicable_number;
}

sub get_prime_divisor {
    my ($ref) = @_;
    my $sum = 1;

    for my $div_pair (@{$ref}) {
        my $prime = $div_pair->[0];
        my $limit = $div_pair->[1];

        if ($limit == 1) {
            $sum *= ($prime + 1);
            next;
        }

        my $mul = 1;
        for my $j (1..$limit) {
            $mul += ($prime ** $j);
        }
        $sum *= $mul;
    }

    return $sum;
}

sub fact_prime {
    my ($num) = @_;

    my @divisor;
    my $times = 0;

    my $limit = sqrt($num);
    while(1) {
        if ($num % 2 == 0) {
            $num /= 2;
            $times++;
        }
        else {
            push @divisor, [2, $times] if $times != 0;
            $times = 0;
            last;
        }
    }

    for (my $i = 3; $i < $limit + 1;) {
        if ($num % $i == 0) {
            $num /= $i;
            $times++;
        }
        else {
            push @divisor, [$i, $times] if $times != 0;
            $times = 0;
            $i += 2;
        }
    }

    push @divisor, [$num, 1] if $num != 1;

    return [@divisor];
}