my $n=1000;

# sieve and recursively compute totient

my @p; # $p[$k] will be largest prime factor of $k
my @t; # $t[$k] will be totient of $k
$t[1]=1; # base case

for ($i=2;$i<$n;$i++) {
    if (!$p[$i]) {
	for ($j=1;$j<$n/$i;$j++) {
	    $p[$i*$j] = $i ;
	    if ($i == $p[$j]) {
		$t[$i*$j] = $i*$t[$j];
	    } else {
		$t[$i*$j] = ($i-1)*$t[$j];
	    }
	}
    }
    print "phi($i) = $t[$i]\n";
}