You can stop your inner foreach my $prime loop once $prime > sqrt($x), I believe... That should be a big win once $max gets large.

Cache the sqrt result before the loop, of course.
--
Mike