Re: interview question on primes


"quasi" <quasi@xxxxxxxx> wrote in message
news:7ar6s39mvi8cgr09h9umkhhjb1r7gjp4l9@xxxxxxxxxx
On Tue, 26 Feb 2008 12:28:27 +1100, "Peter Webb"
<webbfamily@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:


"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.

No, not really.

It's a real world question, not an academic one.

Moreover, the question was not a "take-home project". Presumably it
was expected to solved right then and there, at the interview.

Judgement is required here.

Of course, the applicant can always _ask_ the interviewer about the
range of values, but in my opinion, having to ask that question would
show a lack of common sense. The very fact that the range was not
specified, together with the implied time constraints of the
interview, should be enough for the applicant to opt for a clean,
simple, standard solution.

quasi

The OP was asked to find the primes between A and B. His answer was
essentially to write the simplest of all programs to determine primality and
test all the numbers between A and B. This is about as far from a "real
world" answer as you can get. He was obligated to ask questions to more
accurately determine the scope of the problem. The useful answer then would
be to suggest algorithms that will actually find the primes for values of A
and B appropriate to their absolute and relative magnitudes. Peter Webb
(first responder to the OP's question) gets the job.


.

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)