1. Prime Sieve again
I believe this is a pretty good attempt. On a P75 with 32Mb RAM it managed
all the primes upto 4,000,000 in 6.3 seconds. It achieves this by taking a
leaf out of RDS's book and ignoring all even numbers.
RDS is quicker because it doesn't generate the C sequence {2,3,5,...}
Here it is:
-- ------------------------------------------
-- File = CRWsieve.ex < Sieve of Eratosthenes >
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's not a number! ... \n ")
end if
t1 = time()
n = floor(m[2]/2)
A = repeat(1, n)
C = {2}
for j = 1 to n do -- sqrt(n) + 1 might be quicker here, but will it work?
if A[j] = 1 then
s = j + j + 1
C = C & s -- RDS doesn't do this...
for k = j to n by s do
A[k] = 0
end for
end if
end for
s = length(C)
--? C
printf(1, "%7d \t %7d \t %7d \t %7d \n ", C[s-3 .. s])
printf(1, "\n\n There were %d PRIMES below the number %d \n ",{s-1, m[2]})
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/
2. Re: Prime Sieve again
Carl White, your latest, when I put it on a consistent basis with the others
gave 1.40 seconds vs RDS 1.31. I tried the Hilley trick of no C seq but
still got 1.35 seconds. Bye, Art
> From Carl White who at 11:23 AM 3/11/98 +0000 wrote:
>I believe this is a pretty good attempt. On a P75 with 32Mb RAM it managed
>all the primes upto 4,000,000 in 6.3 seconds. It achieves this by taking a
>leaf out of RDS's book and ignoring all even numbers.
>
>RDS is quicker because it doesn't generate the C sequence {2,3,5,...}
My mod of RDS, on which the timing is based, saves the primes in a
sequence.
>
>Here it is:
>
>-- ------------------------------------------
>-- File = CRWsieve.ex < Sieve of Eratosthenes >
>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's not a number! ... \n ")
>end if
>
>t1 = time()
>
>n = floor(m[2]/2)
>
>A = repeat(1, n)
>C = {2}
>
>for j = 1 to n do -- sqrt(n) + 1 might be quicker here, but will it work?
> if A[j] = 1 then
> s = j + j + 1
> C = C & s -- RDS doesn't do this...
> for k = j to n by s do
> A[k] = 0
> end for
> end if
>end for
>
>s = length(C)
>--? C
>
>printf(1, "%7d \t %7d \t %7d \t %7d \n ", C[s-3 .. s])
>printf(1, "\n\n There were %d PRIMES below the number %d \n ",{s-1, m[2]})
>
>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/
>
Arthur P. Adamson, The Engine Man, euclid at isoc.net
3. Re: Prime Sieve again
On Wed, 11 Mar 1998, Arthur Adamson wrote:
> Carl White, your latest, when I put it on a consistent basis with the others
> gave 1.40 seconds vs RDS 1.31. I tried the Hilley trick of no C seq but
> still got 1.35 seconds. Bye, Art
RDS doesn't do the status printouts withing the t1 to t2 timing loop, as
well as missing out the creation of the C list. My guess is that this will
get me within a hundredth of a second of RDS.
By rights, the last lines of my program *could* read (without trying to
cheat the system):
t2 = time() - t1 -- Notice how these two lines have been moved to compete
-- with RDS...
printf(1, " \n Total time for primes list creation = %6.2f", t2)
s = length(C) -- s is only needed for printout purposes
--? C
printf(1, "%7d \t %7d \t %7d \t %7d \n ", C[s-3 .. s])
printf(1, "\n\n There were %d PRIMES below the number %d \n ",{s-1,
m[2]})
I'm enjoying this. It's great fun :)
BTW, it's not too hard to make this into a prime factoring program, as
someone reckoned would be more useful...
Just find all the primes upto sqrt(n)+1 and then repeatedly divide n by
the primes where it divides evenly. Printout a prime when there's a match.
I did something similar in C based on oprime.ex...
--
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/
