my $max = 10_000; my @sieve = (); # n -> list of rank of primes dividing n my @primes = (1); # n -> n-th prime foreach my $n (2..$max) { if (not $sieve[$n]) { push @primes => $n; my $p = $#primes; my $m = $n; while ($m <= $max) { push @{$sieve[$m]} => $p; $m += $n; } } } my @a = (); $a[1] = 1; sub a { my $n = shift; if (not $a[$n]) { my $a = 1; my $rem = $n; foreach my $p (@{$sieve[$n]}) { my $prime = $primes[$p]; my $pow = 0; while ($rem % $prime==0) { $pow++; $rem /= $prime; } $a *= $p ** a($pow); } $a[$n] = $a; } return $a[$n]; } foreach my $n (1..$max) { my $a = a($n); print "$n $a\n"; }