http://qs321.pair.com?node_id=203844


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

    [download]
    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.

[reply]
[d/l]
[select]
      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."

[reply]
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)
[reply]

In Section Seekers of Perl Wisdom