Re: finding primes

Richard Heathfield wrote:
Digital Puer said:

Got this on an interview question: given two integers A and B,
find all primes between them.

I basically wrote an initial function, bool isPrime(int i), which
loops over all numbers between 2 and sqrt(i) to see if i%num == 0,
in which case the number is not a prime.

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.

- Logan
.

Relevant Pages

  • Re: finding primes
    ... find all primes between them. ... I basically wrote an initial function, bool isPrime, which ... loops over all numbers between 2 and sqrtto see if i%num == 0, ... force (all the mentioned solutions in this thread are brute force) for ...
    (comp.programming)
  • Re: interview question on primes
    ... given two integers A and B, find all primes between them. ... loops over all numbers between 2 and sqrtto see if i%num == 0, ... was expected to solved right then and there, at the interview. ... the applicant can always _ask_ the interviewer about the ...
    (sci.math)
  • Re: interview question on primes
    ... given two integers A and B, find all primes between them. ... loops over all numbers between 2 and sqrtto see if i%num == 0, ... They can't assume that the applicant is a Number ... research project out of it, ...
    (sci.math)
  • Re: interview question on primes
    ... given two integers A and B, find all primes between them. ... loops over all numbers between 2 and sqrtto see if i%num == 0, ... was expected to solved right then and there, at the interview. ... situation (interview time, on the spot) calls for simplicity. ...
    (sci.math)
  • Re: interview question on primes
    ... given two integers A and B, find all primes between them. ... I basically wrote an initial function, bool isPrime, which ... loops over all numbers between 2 and sqrtto see if i%num == 0, ... If A= some 50 digit number and B=A+100, you would probably use a pseudo-prime checking function with brute force used only for checking possible pseudoprimes. ...
    (sci.math)