Problem 26

1000以内の数に対して 1 / nを求めたときに最も長い幅の循環少数になる
nを求めろという問題。素数以外の数は素因数分解したときの一番でかいサイズの
素数に依存するのではないかと思うので、対象は素数のみとする。
方針は wikipediaあたりを参考に決定。 10 / nで循環するのであれば、9/nは
割り切れるはずというのを利用しています。ただし 2とか 5は 10を割りきれて
しまうので、そこだけ注意。この素数判定プログラムは早すぎですね。

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

use bigint;
my @primes = (2);
print "Answer is ", p26(1000), "\n"; # Answer is 982

sub p26 {
    my ($limit) = @_;

    map {is_prime($_)}(3..1000);

    my $max = 1;
    for my $i (@primes) {

        my $count = 1;
        while (1) {
            my $value = 10 ** $count;

            last if $value % $i == 0;
            last if ($value - 1) % $i == 0;
            $count++;
        }
        $max = ($count > $max) ? $count : $max;
    }

    return $max;
}

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

    for my $i (@primes) {
        last if $i ** 2 > $num;
        return 0 if $num % $i == 0;
    }
    push @primes, $num;
    return 1;
}