1. Prime math magic answer.
\\\|/////
\\ - - //
( @ @ )
-- Lucius L. Hilley III -- lhilley at cdc.net --
-- of -- --
-- Hollow Horse Software -- http://www.cdc.net/~lhilley --
----------------------------------------------------------
I thought about the code I had previously examined.
RDS's sieve is multiplying by 2 so that only the odd
numbers are filtered. 2 is the only even number that is
prime. All other prime numbers are odd.
Exactly half the sieving is skipped/eliminated.
--------------Oooo----------------------------------------
oooO ( )
( ) ) /
\ ( (_/
\_)
2. Re: Prime math magic answer.
> I thought about the code I had previously examined.
> RDS's sieve is multiplying by 2 so that only the odd
> numbers are filtered. 2 is the only even number that is
> prime. All other prime numbers are odd.
>
> Exactly half the sieving is skipped/eliminated.
I'm almost positive that after 3, every prime number is plus or minus 1 of
a multiple of 6. 5 (6-1), 7 (6+1), 11 (6*2-1), etc. With that in mind, we
could probably speed up the current algorithms, unless that's already in
there.
---------------------------------------------------
William
ICQ# 1480159
3. Re: Prime math magic answer.
- Posted by MAP <ddhinc at ALA.NET>
Mar 08, 1998
-
Last edited Mar 09, 1998
William Eiten wrote:
> I'm almost positive that after 3, every prime number is plus or minus 1 of
> a multiple of 6. 5 (6-1), 7 (6+1), 11 (6*2-1), etc. With that in mind, we
> could probably speed up the current algorithms, unless that's already in
> there.
Hi,
Take a look at the prime generator I wrote, it uses the very method you
spoke
of. It came in much slower than the two sieve methods used, but still
outperformed the rest of the non-sieve methods. You might try combining
that method with RDS's to see if you can post best-time in it. In my
submission I tried to avoid the methodology of having to pre-form
a sequence and eliminate rejects, but without this kind of
"pre-guessing"
it's hard to produce a fast enough algorithm. So, I'm working on another
program with potentially a "better sieve than sieve". In the first
program,
I used the fact that every non-prime in the set you described has a
prime
as a factor as a means of elimination. In the one I'm working on now,
I'm
using the idea that all the factors of each member in this set are
prime.
i.e. 605 = 11 * 11 * 5. Presently, it runs a much closer third than my
previous one (my calculations show it'd be around 3.5 in the benchmark,
but that's just a guess-timation). Unfortunately I've having a bit of
diffuculty eliminating a small portion of the set (I know where they
are,
just hard to modify the algorithm I'm using to hit them).
When (or if) I fix this I'll post it, and then maybe make a try for
beating
the two sieves posted.
Christopher D. Hickman
