project-euler/Perl/565 Divisibility of sum of divisors.pl at master · trizen/project-euler · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#!/usr/bin/perl

# Daniel "Trizen" Șuteu
# Date: 04 July 2018
# https://github.com/trizen

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

# Runtime: ~4 minutes

use 5.010;
use strict;
use warnings;

use ntheory qw(is_prime divisor_sum logint sqrtint forprimes);

sub S {
    my ($n, $k) = @_;

    my %seen;
    my $sum = 0;

    my $process_term = sub {
        my ($t) = @_;

        for (my $s = $t ; $s <= $n ; $s += $t) {

            next if ($s % $t**2 == 0);

            if (divisor_sum($s / $t) % $k == 0) {
                next if $seen{$s}++;
            }

            if (divisor_sum($s) % $k == 0) {
                $sum += $s;
            }
        }
    };

    forprimes {
        my $p = $_;
        foreach my $e (3 .. 1 + logint($n, $p)) {
            if (($p**$e - 1) % $k == 0) {
                $process_term->($p**($e - 1));
            }
        }
    } sqrtint($n);

    for (my $t = $k ; $t <= $n ; $t += $k) {
        if (is_prime($t - 1)) {
            $process_term->($t - 1);
        }
    }

    return $sum;
}

say S(1e6,  2017);
say S(1e9,  2017);
say S(1e11, 2017);