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

Problem 21

euler perl


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