Re: interview question on primes


"Digital Puer" <digital_puer@xxxxxxxxxxx> wrote in message news:3bdc49e5-d202-491a-bde2-c7c31bee801f@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Got this on a software engineering 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 then
loop between A and B, calling isPrime() on each value.

Any better ideas?

The "correct" answer is heavily dependent on the range of values of A and B, and if this is all the question states, its a pretty poor question.

If A=1,000,000 and B=1,000,100 your approach is viable but probably inefficient.

If A=7 and B=1,000,000 a sieve would be far more efficient.

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.

This question in its current form does not tell the examiner anything about your ability to design algorithms, IMHO.


.

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)
  • interview question on primes
    ... Got this on a software engineering interview question: ... 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, ...
    (sci.math)
  • finding primes
    ... 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, which ... loops over all numbers between 2 and sqrtto see if i%num == 0, ...
    (comp.programming)
  • Re: finding primes
    ... I basically wrote an initial function, bool isPrime, which ... loops over all numbers between 2 and sqrtto see if i%num == 0, ... gcdis the product of all the primes between a and b. ... So it only remains to factorize this one number, ...
    (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, ... They can't assume that the applicant is a Number ... research project out of it, ...
    (sci.math)