A more efficient implementation of Eratosthenes’ sieve?


A quick visual reminder of the pattern I’ve just described in the previous couple of posts, looking at the distribution of “possible primes, or “candidate primes” and non-primes after sieving by the n-th prime, for the first three primes.

PP(n) is the set of “possible primes” after sieving to the n-th prime, and A(n) and B(n) are two sets used to get from PP(n-1) to PP(n), by first repeating PP(n-1) Pn times to yield A(n), then multiplying all “possible primes” within PP(n-1) by Pn to get B(n). PP(n) is obtained by removing all members of B(n) from A(n).

The following boxes show positions of “possible primes” within primorials as “1” and non-primes as “_”:

So to get a progressively tighter determination of “possible primes” and non-primes up to the n-th primorial, all we need to is sequentially repeat the lower primorial pattern, PP(i), P(i+1) times (yielding A(i)) and then stretch it by a factor of P(i+1) (yielding B(i)), then intersect the two sets (yielding PP(i)).

What has gone unsaid thus far, but should be self-evident, is that after sieving to the n-th prime, the set of “possible primes” and non-primes between Pn and Pn^2 are actual primes and non-primes. Hence by doing this sequential repetition, stretching and intersection n times, we obtain the complete set of primes to Pn^2. The final box above shows the pattern of possible primes and non-primes within 5# between 5 and 5^2, which includes only the actual primes 7, 11, 13, 17, 19 and 23.

Exactly the same thing happens for higher primes and associated primorials.

I believe this is a much more efficient implementation of the sieve of Eratosthenes.

Note that as n and Pn grow, the gap between Pn^2 and Pn# grows very quickly. In the image above, the upper end of the range containing confirmed primes (5 to 25) is close to the top of the primorial (30). For P7 = 17, P7^2 = 289 and P7# = 510510. The gap between these values grows exponentially.

I’d like to spend a little time working out how much computational effort is required for sieving to some value x, just for kicks. I imagine the computational effort grows exponentially.

For ease of visualization, here is the same sequence of sieving illustrated, but with the patterns for 2# and 3# extended out over 5# (30):

About petequinn

I'm a Canadian geotechnical engineer specializing in the study of landslides. I started this page to discuss some mathematical topics that interest me, initially this involved mostly prime numbers, but more recently I've diverted focus back to a number of topics of interest in geotechnique, geographic information systems and risk. I completed undergraduate training in engineering physics at Royal Military College (Kingston, Ontario), did a masters degree in civil (geotechnical) engineering at University of British Columbia (Vancouver), and doctorate in geological engineering at Queen's University (Kingston). I was a military engineer for several years at the beginning of my career, and did design and construction work across Canada and abroad. I've worked a few years for the federal government managing large environmental clean up projects in Canada's arctic, and I've worked across Canada, on both coasts and in the middle, as a consulting geotechnical engineer. My work has taken me everywhere in Canada's north, to most major Canadian cities and many small Canadian towns, and to Alaska, Chile, Bermuda, the Caribbean, Germany, Norway, Sweden, Bosnia, and Croatia. My main "hobby" is competitive distance running, which I may write about in future.
This entry was posted in Prime Numbers, Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s