diff options
author | Jesse Luehrs <doy@tozt.net> | 2009-05-17 19:56:10 -0500 |
---|---|---|
committer | Jesse Luehrs <doy@tozt.net> | 2009-05-17 19:56:10 -0500 |
commit | 5127cd8bcbd3760ca3fdf17f0c924336a40a9955 (patch) | |
tree | 94823bc6c07b9fd3983a26170b356932f16b9cb9 | |
parent | 20aecd657d1d70dc0f6f03ac00f1a7e89dd89bd1 (diff) | |
download | projecteuler-5127cd8bcbd3760ca3fdf17f0c924336a40a9955.tar.gz projecteuler-5127cd8bcbd3760ca3fdf17f0c924336a40a9955.zip |
solution to 124
-rwxr-xr-x | 124.pl | 44 |
1 files changed, 44 insertions, 0 deletions
@@ -0,0 +1,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; |