Re: As the Crow flies.

In message <83b7f9ca-051b-4f3d-90e0-b3c54cd7e846@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>, spintronic <spintronic@xxxxxxxxxxx> writes
On Oct 8, 6:41 pm, Ernest Major <{$t...@xxxxxxxxxxxxxxxxx> wrote:
In message
<673323fe-7960-465e-879e-a95ef0539...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Dwib <dwibd...@xxxxxxxxx> writes





>On Oct 8, 11:33 am, spintronic <spintro...@xxxxxxxxxxx> wrote:
>> Quickest algorithm to find all primes below (N).

>> For usenet. (N) = 1000.

>> Please give your working out.

>> And more importantly the number of calculations you use.

>> The winner gets to kiss my ass, when I present mine.

>MatLab has a pretty cool algorithm.  Roughly speaking it is:
>1) They create an array of integers from 1 to N.
>2) For each integer, i, from 2 to root-N (I think), they "zero" every
>i-th element.
>3) What's left over are the prime numbers.

In the Sieve of Erastothenes the second step is

2) For each prime number (i.e.number not struck out by previous passes)
from 2 to root(N).

Wikipedia gives a more efficient algorithm - the Sieve of Atkin.



>Pretty cool!

>Dwib

--
alias Ernest Major- Hide quoted text -

- Show quoted text -

Am I correct in thinking that for PI(1000) this takes 301 calculations?

Are you counting demonstrating that 2, 3 and 5 are prime in that figure? [1] (Since you object to taking the primes < 1000 from a table, you should also object to taking the primes < 6 as precalculated.)

Apart from that, your question, like your original post to this thread, is ill-posed. The number of calculations is implementation dependent; it also depends on what is defined as a calculation. (How many calculations did you assign to the calculation of floor(root(1000))?)

Also, why did you pick such a tidgy number for measurement of speed? - an algorithm that is faster for PI(1000) might be left behind in the dust for PI(1000000000).
--
alias Ernest Major

.

Relevant Pages

  • Re: As the Crow flies.
    ... alias Ernest Major- Hide quoted text - ... The number of calculations is implementation dependent; ... If it isn't, then 2095 calculations is pretty steep, and my algorithm ... James Harris's prime counting function. ...
    (talk.origins)
  • Re: As the Crow flies.
    ... If you've got an algorithm that ... alias Ernest Major- Hide quoted text - ... So, while I don't have implementations to hand, I expect that the run times for implementations of Legendre's, Lehmer's or Meissel's functions would also be too fast to measure for a value of 997. ... when you started the thread you were talking about generating a list of the primes upto 1000. ...
    (talk.origins)
  • Re: Math errors in book Secret Life of Numbers
    ... his students have proven that primes can be found in polynomial time. ... For practical purposes the algorithm is, admittedly, still too ... that in practice, it always was solved in polynomial time using the ... the simplex method is not a polynomial-time algorithm. ...
    (sci.math.research)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.math)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.crypt)