use POSIX;
$| = 1;

%rad = ();
$rad{1} = 1;
for (my $i = 2; $i <= 100000; $i++) {
	$q = multFact($i);
	$rad{$i} = $q;
}

@sortkeys = sort sortfunc keys %rad;
$x = 1;
foreach (@sortkeys) {
	$x++;
}
print "E(10000) = " . $sortkeys[9999] . "\n";

exit;

sub sortfunc {
	return 1 if ($rad{$a} > $rad{$b});
	return -1 if ($rad{$a} < $rad{$b});
	if ($rad{$a} == $rad{$b}) {
		return 1 if ($a > $b);
		return -1 if ($a < $b);
	}
	return 0;
}


sub multFact {
	my $n = shift;
	$tot = 1;
	my @f = factors($n);
	$tot *= $_  foreach (@f);
	return $tot;
}

sub factors {
	my $x = shift;
	my %div = ();
	$count = 0;
	for (my $j = 2; $j <= sqrt($x); $j++) {
		while ($x % $j == 0) {
			$div{$j} = 1;
			$div{($x / $j)} = 1 if (isprime(($x / $j)));
			$x /= $j;
			$count = 1;
		}
	}
	$div{$x} = 1 if ($count == 0);
	return (keys %div);
}

sub isprime {
    my $num = $_[0];
    my $val = 'prime';
    if ($num =~ /^\d+$/ && $num >= 2) {
        my $mod = 2;
        my $div = int sqrt $num;
        while ($mod <= $div) {
            ($num % $mod) == 0 ? ($val = 'composite', last) : $mod++;
        }
    } else { $val = 'neither'; }
    if ($val eq 'prime') {
      return 1;
    } else {
      return 0;
    }
}