Re: finding primes

"Digital Puer" <digital_puer@xxxxxxxxxxx> writes:
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. With this function I loop
between A and B, calling isPrime() on each value.

Is there a better way to do this? I looked at the Sieve of
Eratosthenes,
which didn't seem to be much better.

Complexity of euclidian gcd(a,b) is O(log(max(a,b))).
gcd(a,b) is the product of all the primes between a and b.

So it only remains to factorize this one number, instead of
factorizing both a and b, for which you have to compute the primes
only up to sqrt(gcd(a,b)) at most.

O(sqrt(gcd(a,b))+log(max(a,b)))



--
__Pascal Bourguignon__ http://www.informatimago.com/

"Do not adjust your mind, there is a fault in reality"
-- on a wall many years ago in Oxford.
.

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. ... 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)
  • 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)