11/7    Re: "Teaser: write an algorithm for finding prime numbers." on 11/1,
        I wrote some C code to find all prime numbers between 1 and 4294967295
        with 32-bit math (no 64-bit or floating-point math).  It took about 84
        hours on a 502MHz Sun-Blade-100.
        \_ Quickly thought through, totally untested alg.
           Make a list of (n, n^2) tuples for all n < 2^16 and n is prime.
           For all numbers from 2^16 to 2^32 go through the list
             if n^2 > number you are prime, break.
             if number % n = 0 you are not prime.
           \_ That's more or less what I do in my 13-KByte 83-hour algorithm,
              except that I only keep a list of n instead of (n, n^2).  I'll
              try the sieve method.  --- OP
        \_ So I ran: % nice +20 primes 1 4294967295 > primes.txt
           on my 800MHz Athlon.  It took 8 minutes on the nose.
           % wc -l primes.txt
           203280221 primes.txt
           --dbushong
           \_ Wow!  Must be a better algorithm.  Where's the source code?
              Better yet, what's the algorithm?  Thx.  -- OP
              \_ Pretty standard sieve of eratosthenes:
                 http://www.freebsd.org/cgi/cvsweb.cgi/src/games/primes
                 --dbushong
                 \_ What's the memory usage?  Mine is ~26KB.  -- OP
                 \_ What's the memory usage?  Mine is ~13KB.  -- OP
                    \_ IIRC, it was a few megs --dbushong
        \_ Did you go from 1 to N or 1 to sqrt(n). That would speed things up.
           \_ I go from 1 to sqrt(n).  -- OP
              \_ are you avoiding even #'s? how about factors of 3, 5, 7, etc.
                 that's basically what "primes" is doing.
                 \_ but there are easier tests for divisibility for smaller
                    primes than there are for larger ones.  also, a test for
                    divisibility by 2, 3, 5, 7 and other smaller primes do
                    more to knock out parts of the field.