Here's the code I've used for this in the past. I believe it's fairly efficent. If you're going to use it like in the root node in this thread, it's best to check only odd numbers, as suggested by ichimunki.

#!usr/bin/perl -w
use strict;
sub prime {
my $number = shift;
my $d = 2;
my $sqrt = sqrt $number;
while(1) {
if ($number%$d == 0) {
return 0;
}
if ($d < $sqrt) {
$d++;
} else {
return 1;
}
}
}
my $number = $ARGV[0];
print prime($number);

nope! they all look prime to me!
i like it, i'm gonna use it to explain programming loops to a mathmatician friend. i took the liberty to re-arrange a touch...

sub isPrime
{
my $number = shift;
my $sqrt = sqrt $number;
my $d = 2;
while (1)
{
return 0 if ( $number % $d == 0 );
return 1 if ( $d > $sqrt );
$d++;
}
}

In fact, you're right, because numbers which only can be devided in 1, themselves and their square root will be marked as prime in this way. make the < into a <= and it is solved.