summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJesse Luehrs <doy@tozt.net>2009-05-17 19:56:10 -0500
committerJesse Luehrs <doy@tozt.net>2009-05-17 19:56:10 -0500
commit5127cd8bcbd3760ca3fdf17f0c924336a40a9955 (patch)
tree94823bc6c07b9fd3983a26170b356932f16b9cb9
parent20aecd657d1d70dc0f6f03ac00f1a7e89dd89bd1 (diff)
downloadprojecteuler-5127cd8bcbd3760ca3fdf17f0c924336a40a9955.tar.gz
projecteuler-5127cd8bcbd3760ca3fdf17f0c924336a40a9955.zip
solution to 124
-rwxr-xr-x124.pl44
1 files changed, 44 insertions, 0 deletions
diff --git a/124.pl b/124.pl
new file mode 100755
index 0000000..3ed41e1
--- /dev/null
+++ b/124.pl
@@ -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;