|
 |
Warp wrote:
> Orchid XP v7 <voi### [at] dev null> wrote:
>> -#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-
>> -###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-
>> -#####-###-#-###-#-#####-#-###-#-###-#####-###-#-###-#-#####-###-#-###-
>
> That last pattern is wrong.
Right. Well I typed these out by hand, so if there are errors then it's
because my typing is inaccurate. :-S
> Anyways, using the correct patterns, wuldn't it be better to preserve
> the info about which of those are the primes?
> If we mark untested numbers with '-', primes with '!' and non-primes
> with '#' then that would become:
>
> -!-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-
> -!!#-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-
> -!!#!#-###-#-###-#-###-#####-#-###-#-###-#-###-#-###-#####-#-#####-###-
> -!!#!#!###-#-###-#-###-#####-#-#####-###-#-###-#####-#####-#-#####-###-
>
> etc.
>
> In the end you end up with:
>
> -!!#!#!###!#!###!#!###!#####!#!#####!###!#!###!#####!#####!#!#####!###
Well, then you'd need more bits per number. (I'm using a simple bitmap
at the moment.) Still, it could work...
> OTOH using this algorithm you basically need to fix the number of
> primes you want to calculate. It also requires random access so it's
> not very usable with linked lists.
Yeah, pretty much.
For finding "really big" prime numbers, it seems that space rather than
time is going to be the issue. The algorithm more or less forces you to
go up in predetermined step sizes. I would think you'll run out of RAM
fairly quickly.
It's not entirely clear to me that this algorithm is any faster or
otherwise "better" than the normal seiving algorithm. (As in, if you
want all primes below N, find all primes below sqrt(N) and then sieve a
larger list from 1 to N. And possibly find the smaller primes list by
the same method recursively.)
It's certainly an "unusual" algorithm though. At least, I've not seen it
before...
Post a reply to this message
|
|
