Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re: YAPNC: Yet another prime number checker?

by Abigail-II (Bishop)
on Oct 09, 2002 at 07:24 UTC ( [id://203850]=note: print w/replies, xml ) Need Help??


in reply to 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"
    Abigail

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://203850]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others musing on the Monastery: (4)
As of 2024-04-25 14:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found