|
 |
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...)
Post a reply to this message
|
|
