OpenEuphoria

Re: Prime math magic answer.

• Posted by MAP <ddhinc at ALA.NET> Mar 08, 1998
• 600 views

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