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

初代Masteries

きっとモヒカンにもなれないお前たちに告げる!!!

Project Euler - Problem 23

Problem 23

問題を解くのが結構キツくなってきました. ...もうちょっと頑張ります.

この問題は, 2つの過剰数の和で書き表すことができない整数の総和を求める問題.
過剰数とは, ある数の約数の和がその数よりも多いものを指すようです.
で, 数学的な解析により28123より大きい任意の整数は2つの過剰数の和で書けることがわかっているので, 28123を探索範囲の上限にすればよいみたいです.

use strict;
use warnings;
use List::Util qw/sum/;

my $abundants = {};

my $max = 28123;

for my $i (1..$max) {
    $abundants->{$i} = 1 if sum_factors($i) > $i;
}

my $total = 0;
for my $i (1..$max) {
    unless (sum_abundant($i)) {
        $total += $i;
    }
}
print $total;

sub sum_abundant {
    my $n = shift;

    for my $abundant (sort {$a <=> $b} keys %{$abundants}) {
        return 1 if $abundants->{$n - $abundant};
    }
    return 0;
}

sub sum_factors {
    my $n = shift;

    return 1 if $n == 1;

    my @divs = grep { $n % $_ == 0 } 1..sqrt($n);
    push (@divs, map { $n == $_ ** 2 ? () : $n / $_ } reverse @divs[1..$#divs]);

    return sum(@divs);
}

...というわけで解けはしましたが, そこそこ時間がかかるのでかなりダメダメですね.
いずれ実行時間の短縮を目指したいところです.