Orchid XP v7 wrote:
> I posted this in one of the Haskell groups a few days ago - but it's 
> actually not to do with Haskell particularly, so...
> 
> I've stumbled on a slightly unusual way to find prime numbers. It goes 
> like this. Suppose you're sitting here seiving prime numbers. We start 
> by deleting 2 and all its multiples. That leaves us with a pattern like 
> this:
> 
> -#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-
> 
> Ignoring 1, the next place that has a dash is 3, so 3 is the next prime 
> number. Deleting 3 and all its multiples, we get
> 
> -###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-
> 
> In other words, an infinite list of twin "primes". Well anyway, the next 
> uncrossed number is 5, so 5 is prime. Deletin 5 and all its multiplies 
> yields
> 
> -#####-###-#-###-#-#####-#-###-#-###-#####-###-#-###-#-#####-###-#-###-
> 
> And so forth. At each stage, we get a longer repeating pattern. If you 
> take each of these lines and snip it down to just 1 repartition, you get
> 
> Initial: (-)
> After 2: (-#)
> After 3: (-###-#)
> After 5: (-#####-###-#-###-#-###-#####-#)
> 
> The first pattern is 1 units long, the next is 2*1 = 2 units long, the 
> next is 3*2 = 6 units long, and the last one is 5*6 = 30 units long. The 
> "after 7" pattern is 7*30 = 210 units long, so I won't bother writing it 
> out here. ;-)
> 
> You can use all this to write an algorithm for finding primes. Basically 
> start with some pattern, find the next prime P (first uncrossed square 
> ignoring 1), repeat the pattern P times, seive out all multiplies of P, 
> go back to step 1. (In practice, you have to start from the "after 3" 
> pattern for this to work properly.)
> 
> Initial:  -###-#
> Find   P: 5
> Repeat P: -###-#-###-#-###-#-###-#-###-#
> Seive  P: -#####-###-#-###-#-###-#####-#
> Find   P: 7
> etc.
> 
> Actually, every dash in the grid (up to sqrt(grid size) is a prime 
> number). So after less than a dozen iterations of this (very simple) 
> algorithm, you can find all primes below 1,000,000. (!)
> 
> (Notice that the "normal" seiving algorithm keeps 5 and deletes only 
> higher multiples of it. My algorithm deletes 5 itself as well. It must 
> for the algorithm to work right...)

The pattern that you have to keep and process for each prime grows 
factorially.  Doesn't look too big for small n but it certainly takes 
off quickly.

So by the time that you are able to deliver say the 1000th prime number, 
the pattern would be *rather* large.  And you need to keep maintaining 
the growing pattern to continue delivering the 1001st, 1002nd etc.

If you choose to stop accumulating the pattern at some point then you 
are back to classic Sieve of Eratosthenes with a slightly different way 
to build up the array to its desired size.

I know you were just offering an insight not thinking it was actually 
practical.

How about we call this Orchid's Algorithm - because it is 'bloomin 
ridiculous' :)

Post a reply to this message