What made you believe that the program hang? One thing is for sure that, the program will run for quite a while before it finally figures out that 429496731 is a prime.

You don't need to test every integer that is smaller than the input number. You only need to try up to its sqrt(). (You can further improve this, but what I suggested here is an easy fix to the situation with the least amount of effort.)

#!/usr/bin/perl

use strict;
use warnings;
use Math::Prime::XS qw(is_prime);

my $prime = shift @ARGV;
if (is_prime($prime)) {
        print "prime", "\n";
}
else {
        print "not prime", "\n";
}
[download]

First things first-- please use the code tag around your source code. Also, preview is a wonderful idea before creating a post.

How do you know the code is hanging? Consider putting some logic in that will update you every x numbers in the loop. Basic debugging is a good skill to learn, and usually starts with a print. Now consider that you only have to check the numbers up to the square root of the number you are testing for prime, and you only need to check the odds after the number 2.

...and really you only have to check other primes (they're all odd numbers) after 2, which I suppose you could generate over time in an array, at least to some orders of magnitude, so that subsequent calls to said routine were further optimized...

...and really you only have to check other primes (they're all odd numbers) after 2, which I suppose you could generate over time in an array, at least to some orders of magnitude, so that subsequent calls to said routine were further optimized...

That's what I was going to suggest. If you created an is_even function, you could rule out (on average) half of your iterations by ruling out the even numbers first. Of course that would require a special case where n=2, but that would be a single-liner.

Even as optimized as you can be, throwing it really large numbers will always take a very long time, so to give the user some kind of indication that your program is not hung, consider putting in some type of progress indicator. Since you know what the number is, you'd know about how many factors you'd have to check (is it 1 to n, or something else that's fixed?) so you could add something like this:


# Used for progress indicator
select STDERR;
$| = 1;

...


# Progress indicator, final value
$progress = ($count / $total_count) * 100;
printf "Progress: %4.1f\%\r",$progress;
# Set carriage returns back to normal after progress indicator is comp
+lete
select STDOUT;
print "\n";
$| = 0;
[download]

This works really well for a script I use that connects to several hundred servers. Of course it's only useful when you're executing it from a shell, as opposed to cron or some other background process.

Hope that helps.

You really should use a smarter algorithm. You are testing a huge amount of numbers that can't possibly matter. JavaFan above has the right idea.

Here's a prime testing function I was noodling around with for comparison. It tests for primality up to 2**32 in about 1/10 sec on my not very fast computer. (Still unrealistically slow for large numbers of tests but ok for the odd single test here and there.)

Updated: fixed error

use warnings;
use strict;
use Time::HiRes qw/ tv_interval gettimeofday/;

my $time0 = [gettimeofday];

# simple routine to test for primality.
# don't expect sensible results for numbers above 2**32
# on 32 bit OSs.

my $test  = shift @ARGV || 2**32 - 5;    # number to test
my $max   = $test**.5;                   # square root of number to te
+st.
my @primes;
my $isprime;

@primes = ( 2, 3 );                      #seed the primes array

# generate the prime test array.
# save it and load it from a file for faster speed.

my $this = $primes[-1];
while ( $this < $max ) {
    $this += 2;
    my $sqrt = $this**.5;
    for (@primes) {
        if ( $_ > $sqrt ) {
            push @primes, $this if $this < $max;
            last;
        }
        next if $this % $_;
        last;
    }
}

for (@primes) {    # test number
    next if $test % $_;
    $isprime = 1;
}

my $elapsed = tv_interval( $time0, [gettimeofday] );

print "$test is ", ( $isprime ? 'not prime.' : 'prime.' ),
  " In $elapsed seconds.";
[download]