Re: interview question on primes

In article
<31215dba-42e7-476e-9771-27f9b746dee8@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Digital Puer <digital_puer@xxxxxxxxxxx> wrote:

Well, I passed the interview, so I think the interviewer
at least thought my solution was reasonable. However, the
reason I'm asking sci.math this question (as opposed to
one of the programming newsgroups) is to get some insight
from mathematicians. Given my exhaustive search solution,
what's a better solution that could be presented in 5-10
minutes? I am not a number theorist.



On Feb 25, 5:28 pm, "Peter Webb"
<webbfam...@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
If A=7 and B=1,000,000 a sieve would be far more efficient.


Are you referring to the Sieve of Eratosthenes algorithm?
That needs to start at 1, right?

I'm not certain what Peter Webb had in mind,
but let me change the problem a little and give a possible answer.

Suppose you have to find all the primes between
500,000 and 1,000,000.

First use the Sieve of Eratosthenes to find all the primes
up to 1,000 (because 1,000 is the square root of 1,000,000).

Then sieve the numbers from 500,000 to 1,000,000 by those primes.
That is, delete all the multiples of 2, then of 3, of 5, etc. All the
numbers that are still there after you've sieved by the primes up to
1,000 are primes.

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.

Can you give me a URL for further information on this approach?

http://primes.utm.edu/ might be a good place to start.

If "brute force" means "trial division up to the square root"
then I don't think it's any good even to check a single
50-digit number.

--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)
.

Relevant Pages

  • Re: greatest multiple algorithm
    ... Bernstein or Galway's quadratic form sieve rather than ... lower or smaller primes in bit sieve. ... slower with larger sieve sizes due to the large number of memory accesses. ... You can use a wheel to decrease the memory requirements. ...
    (comp.lang.asm.x86)
  • Re: greatest multiple algorithm
    ... Bernstein or Galway's quadratic form sieve rather than ... lower or smaller primes in bit sieve. ... slows down based on size memory used ... You can use a wheel to decrease the memory requirements. ...
    (comp.lang.asm.x86)
  • Re: How to write a efficient Sieve of Eratosthenes algorithm in lisp?
    ... the ultimate test is to find primes in range 999900000 - ... Also, my sieve algorithm is n log, so even if the space ... (loop for x from (start-index n) ... Real time: 0.4375 sec. ...
    (comp.lang.lisp)
  • Re: As the Crow flies.
    ... Almost any sieve would do. ... counting primes < 1000000 ... mark.c:50: warning: return type defaults to ?int? ... mark.c:56: warning: format ?%lld? ...
    (talk.origins)
  • Re: Segfault City
    ... C offers no guarantee that there is any character with a code point ... Not those exact words, but yes, it's true that the Standard offers no such ... but I am in the mood to write a Sieve. ... Number of primes in the sieve: ...
    (comp.lang.c)