Problem 23

過剰数の和で表せない数の合計を求めろという問題。上限がわかっているので、
配列を使ってといてみた。若干 Lisp風に考えてみたかなって思ったけど、全然
そんなことはないかな。約数の和を求めるのは過去の資源を再利用。

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

print "Answer is ", p23(28123 - 1), "\n"; # Answer is 4179871

sub p23 {
    my ($limit) = @_;
    my @abundant;

    for my $i (2..$limit) {
        my $sum = get_prime_divisor(fact_prime($i)) - $i;
        push @abundant, $i if $sum > $i;
    }

    my @array = (1..$limit);
    for my $i (@abundant) {
        for my $j(@abundant) {
            next if $i + $j > $limit;
            $array[$i+$j-1] = 0;
        }
    }

    my $sum = 0;
    map {$sum += $_ if $_ != 0}@array;

    return $sum;
}

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];
}