project-euler/Perl/132 Large repunit factors.pl

#!/usr/bin/perl

# Daniel "Trizen" Șuteu
# License: GPLv3
# Date: 13 May 2017
# https://github.com/trizen

# https://projecteuler.net/problem=132

# Runtime: 5 min, 14 sec

use 5.010;
use strict;
use warnings;

use ntheory qw(:all);

my $n     = 1e9;
my $count = 40;
my $iter  = prime_iterator();

my $factors_sum = 0;

while (my $p = $iter->()) {

    gcd($n, $p) == 1 or next;

    my $sum    = 0;
    my $period = 0;

    foreach my $k (0 .. $p) {
        $sum += powmod(10, $k, $p);
        $sum %= $p;
        $period += 1;
        $sum == 0 and last;
    }

    if ($sum == 0 and $n % $period == 0) {
        $factors_sum += $p;
        say "[$count] $p is a prime factor -> $factors_sum";
        last if --$count <= 0;
    }
}

say $factors_sum;