Re: YAPNC: Yet another prime number checker?

This is a very inefficient algorithm. What you are doing is counting all the divisors of a number (with the exception of divisors divisible by 5) and call it a prime if there are just 2 divisors (special casing a few numbers).

It's of course a lot more efficient to decide a number is prime as soon as you have found a divisor > 1 and smaller or equal to sqrt (number). No need to do millions of divisions to decide 100000000 is prime after finding out it's divisible by 2.

Abigail

Comment on Re: YAPNC: Yet another prime number checker?

Replies are listed 'Best First'.
Re: YAPNC: Yet another prime number checker? by Abigail-II (Bishop) on Oct 09, 2002 at 14:45 UTC
`# Yeah, anything less than 2 is prime.... ;-) $ARGV[0] % $_ or die "$ARGV[0] is composite\n" for 2 .. sqrt $ARGV[0]; die "$ARGV[0] is prime\n"` [download] Abigail	[reply] [d/l]