124.pl


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

#!/usr/bin/perl
use strict;
use warnings;
use 5.010;
use Math::Prime::XS qw/sieve_primes/;
use Heap::Simple;
use List::MoreUtils qw/uniq/;
use List::Util qw/reduce/;

my @primes = sieve_primes(1e5);
my %factors;

sub factors {
    use integer;
    my ($n_orig) = @_;
    my @ret;
    my $prime_idx = 0;
    my $n = $n_orig;
    while ($n > 1) {
        my $prime = $primes[$prime_idx];
        if (exists $factors{$n}) {
            push @ret, @{ $factors{$n} };
            last;
        }
        elsif (($n / $prime) * $prime == $n) {
            $n /= $prime;
            push @ret, $prime;
        }
        else {
            $prime_idx++;
        }
    }
    $factors{$n_orig} = \@ret;
    return @ret;
}

our ($a, $b);
my $heap = Heap::Simple->new(elements => 'Any');
for my $n (1..100000) {
    my $rad = reduce { $a * $b } uniq factors($n);
    $heap->key_insert($rad * 1e5 + $n, $n);
}
$heap->extract_top for 1..9999;
say $heap->extract_top;