OpenEuphoria

That prime number program...

• Posted by "Carl R. White" <C.R.White at SCM.BRAD.AC.UK> Mar 03, 1998
• 694 views

For some reason, I've been receiving quite a bit of attention over the
prime number program I've got in my Euphoria filestore.

Art Adamson has improved on the original design, and I'm believing his
claims as I haven't tested it yet, but it seems to run pretty fast.

However, a couple of months ago I received a post from Bob Hancock,
reminding me of the sieve of Eratosthenes. This is probably the fastest
algorithm for a small number of primes. We came up with many versions, and
kept bouncing them back and forth.

I include one of the many versions below this is my fastest paraphrase
of it... Bob, I hope you don't mind :)

 --  ------------------------------------------
 --  File = P_Sieve.ex  < Sieve of Eratosthenes >
 --  By Bob Hancock. Optimisation by Carl R. White (Cyrek)

include get.e

integer n, s
atom t1, t2
sequence A, C, m

puts(1, "\n List All PRIMES, up to What Number ?  ... \n")
m = get(0)

if m[1] != GET_SUCCESS then
    puts(1, "\n That wasn't a number! ... \n ")
    abort(0)
end if

t1 = time()

n = m[2]

A = repeat(1, n)
C = {} -- Contains (will contain) list of primes from 1 - n

for j = 2 to n do
    if A[j] then
        for k = 2*j to n by j do -- j+j rather than 2*j might be faster
            A[k] = 0
        end for
        C = C & j
    end if
end for

puts(1, "\n\n")

s = length(C) + 1

printf(1, "%7d \t %7d \t %7d \t %7d \n ", C[s-4 .. s-1])
printf(1, "\n\n There were %d PRIMES !   ... below the number %d \n  ", {s-2, n}
)

t2 = time() - t1
printf(1, " \n Total time = %6.2f", t2)

--
Carl R White - "Infinity equals Zero in more ways than (just) one - CRW"
E-mail...: cyrek- at -bigfoot.com              / Remove the hyphens before
Finger...: crwhite- at -dcsun1.comp.brad.ac.uk \ mailing or fingering...
Url......: http://www.bigfoot.com/~cyrek/