Bug! The for loop from one call to prime can clobber the $i of a loop in progress in a parent call.

for($i=3;$i<=sqrt($n);$i+=2){
should be
for(my $i=3;$i<=sqrt($n);$i+=2){

Use use strict!