Re: finding primes

Logan Shaw said:

Richard Heathfield wrote:

This is risky if i is not a perfect square, since sqrt(i) will be
fractional, and you'll lose the fraction on conversion to an int, so you
won't /quite/ be testing right up to the square root.

Actually, I believe it is sufficient. It's just harder to see why.

Here's the reason: you need to test all the integers in the range
from 2 up to sqrt(i), inclusive on both ends. If sqrt(i) isn't an
integer, then ceil(sqrt(i)) is the next integer. But since sqrt(i)
isn't an integer, ceil(sqrt(i)) > sqrt(i). Therefore, you do not
need to test that integer -- it's outside of the range you need to
test. Testing up to floor(sqrt(i)) is sufficient.

Oh. Um, DUH. Sorry, Logan, yes, you are quite right. I guess I was shooting
from the hip again.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
.

Relevant Pages

  • Re: finding primes
    ... Richard Heathfield wrote: ... This is risky if i is not a perfect square, ... fractional, and you'll lose the fraction on conversion to an int, so you ...
    (comp.programming)
  • Re: finding primes
    ... This is risky if i is not a perfect square, ... fractional, and you'll lose the fraction on conversion to an int, so you ...
    (comp.programming)