Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re: YAPNC: Yet another prime number checker?

by JaWi (Hermit)
on Oct 09, 2002 at 06:56 UTC ( #203844=note: print w/replies, xml ) Need Help??


in reply to YAPNC: Yet another prime number checker?

First of all: the used algorithm passed '1' for a prime while it isn't! A prime should have two and only two different integer divisors...

Secondly, you could speed things up a little more: you only need to check all integer numbers up to ceil( $input / 2 ) because of the commutative properties of integers (2*3 == 3*2).
Furthermore, prime are always (except for '2', so almost always) odd numbers, so you could skip them in your test for even more speed improvement!

-- JaWi

"A chicken is an egg's way of producing more eggs."

Replies are listed 'Best First'.
Re: Re: YAPNC: Yet another prime number checker?
by nefertari (Chaplain) on Oct 09, 2002 at 07:32 UTC

    You can stop at sqrt($input).

    Example:
    The divisors of 100 are:
    1, 2, 4, 5, 10, 20, 25, 50, 100. They come in pairs as follows:

    1*100 = 100 2*50 = 100 4* 25= 100 5*20 = 100 10*10 =100 20*5= 100
    and so on. So at 10 which is sqrt(10) you are at the point where the second factor is smaller than the first and you have already tested for this pair.

      nefertari++: You're absolutely and totally right! Well, even less cycles to perform :-)

      -- JaWi

      "A chicken is an egg's way of producing more eggs."

Re: Re: YAPNC: Yet another prime number checker?
by martymart (Deacon) on Nov 22, 2002 at 15:02 UTC
    I don't know if you could work this in, might mean even less cycles; discount any number that ends in a 5 or 0 (25, 50, 165) 'cause they're all multiple of 5 (except 5 itself that is) (actually 0 is already covered as its a multiple of 2)

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (5)
As of 2022-08-14 00:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?