Re: simple algorithm for finding primes

From: Paul Hsieh (qed_at_pobox.com)
Date: 12/10/03 

Date: Wed, 10 Dec 2003 04:10:28 GMT

someone says...
> Paul Hsieh" <qed@pobox.com> wrote:
> > In article <3fd57e8e@funnel.arach.net.au> says...
> > > Sieve of Eratosthenes:
> > >
> > > Make a list of all the integers less than or equal to n (and greater
> > > than one). Strike out the multiples of all primes less than or equal to
> > > the square root of n. Then the numbers that are left are the primes.
> >
> > This discussion is probably better suited to something like
> > comp.programming. They are not much into algorithms or non-C related
> > subjects at all around here. But in any event, here's a nice little Sieve
> > of Eratosthenes for you:
> <snip>
> I tried the code from the link http://www.pobox.com/~qed/32bprim.c
> and indeed it's a little faster then mine (10%-15%)

Well it includes the Sieve of Eratosthenes within the source. It also includes
a kind of "parallel small prime divisor test" (using gcd!) before I bring out
the big guns (Strong-Pseduo-Prime test.) Given that you don't seem to care
about memory usage, you can easily crank the performance for small primes such
as all those < 10^6 by simply increasing the size of the sieve (QF_SIEVE_SIZE)
as desired.

> but it's pretty comlicated and requires a good understanding of both math
> and c, and like you said, is better suited to comp.programming, and unestly,
> i did not understand all of it.

Well, completely understanding it may be a tall order. But I give references
for the math-related algorithms, so you can study those at your leisure. What
is worth-while *understanding* in my algorithm is that it takes roughly the
same amount of time (once it gets past the sieve, and trivial divisors, I mean)
regardless of the size of the input.

Your algorithm is a fine, simplistic algorithm, however it really only works
because you determine the entire sequence of primes one after another. But
for longer and longer sequence of primes it will get slower and slower and
you'll run out of memory sooner or later. 

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

Relevant Pages

  • Re: APL and (very) large arrays
    ... Sort is at best O) depending on the sorting algorithm used, ... As to the OP's question about primes, there are advanced efforts to compute pifor very large values of n, but the only elementary method is to find all primes <= n and count them. ... By representing only the odd values the sieve would require 62.5MB. ...
    (comp.lang.apl)
  • Re: Prime Number Question
    ... were discovered a simply algorithm for generating all prime numbers ... directly, in batches, with each batch being used ... the current best factoring method, the number field sieve, only becomes ... characteristic of primes ...
    (comp.unix.bsd.openbsd.misc)
  • Re: Prime Number Question
    ... were discovered a simply algorithm for generating all prime numbers ... directly, in batches, with each batch being used ... the current best factoring method, the number field sieve, only becomes ... characteristic of primes ...
    (comp.unix.bsd.openbsd.misc)
  • Re: Prime Number Question
    ... were discovered a simply algorithm for generating all prime numbers ... directly, in batches, with each batch being used ... the current best factoring method, the number field sieve, only becomes ... characteristic of primes ...
    (comp.unix.bsd.openbsd.misc)
  • Re: Prime number in assembly?
    ... The disk file is written to only ... Reading the list of primes out from disk would ... > seem to me to be slower that this so it seems more reasonable to ... > through to get a sieve to run fast indicate to me that one ...
    (alt.lang.asm)