Re: finding primes


Digital Puer wrote:
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.

None of the methods listed here in this thread is the right method.

If the numbers are small (e.g. 33002 and 40000) then any method that
works will be good enough (they will finish in an eyeblink). If the
numbers are large (e.g. 4611686018427387904 and 4611686018427389999)
then none of the methods listed in this thread will work unless you
have a lot of patience. And if the numbers are even larger (e.g.
1418571425390253304739712446169831673 and
1418571425390253304739712446169839997) then the methods listed have no
hope of solution. Typically, where these questions are of importance
is where the numbers are stupendously large (IOW one hundred digits or
more).

The best real answer would be to use a hybrid technique with brute
force (all the mentioned solutions in this thread are brute force) for
small problems and more efficient methods for large numbers.

For bigger numbers, I would do something like this:

for (test_number = smallest_value; test_number <= largest_value;
test_number++)
{
bool maybe_prime = miller_rabin_pseudo_prime_test(test_number);
if (maybe_prime) {
bool is_prime = APR_CL_TEST(test_number);
if (is_prime) display_number(test_number);
}
}

or something along those lines. It may be counter intuitive, but a
better place to ask is news:sci.crypt since they deal with things of
that nature all the time. Probably, they can give a better solution
than mine.

.

Relevant Pages

  • 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)
  • 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, ... was expected to solved right then and there, at the interview. ... the applicant can always _ask_ the interviewer about the ...
    (sci.math)