My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum

LinkBack Thread Tools Display Modes
November 6th, 2008, 08:13 AM   #1
Global Moderator
CRGreathouse's Avatar
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Listing primes: a personal history

I've been writing program to enumerate primes since grade school. I thought that a description of the various algorithms I used might be instructive... or at least give you a chance to laugh at me.

I hope this will be useful for cknapp, afreude, and anyone who wanders by.

1. Worse Than You Thought Possible: O(n^2)
I read the definition of prime numbers and wrote a program directly from it. For each n in the range I was testing, I counted the number of divisors. If it was exactly two, I printed the number. At least the memory use was constant!
A non-improvement I made to the program was to test from 2 to n-1 and set a flag if a number divided n.

2. Really bad (but better): O(n^2/log n)
Just like the above, but terminating early if it found a factor. Each composite took time O(sqrt(n)), while each prime took time O(n), for a total of O(sqrt(n) * n + n * n/log n) = O(n^1.5 + n^2/log n) = O(n^2/log n).

3. A vast improvement: O(n^1.5)
I wish I could say that I invented this method, but in fact I read the idea. It immediately made sense, and cut the time for checking primes dramatically. Memory use was still constant, but the time speedup was so dramatic that I could generate primes faster than I could print them (to a printer).
I did realize on my own that I could further improve this by checking only odd numbers and odd divisors. This doubled the speed, but gave no asymptotic improvement. I also saw that I could further improve the process (by wheel sieving, but I didn't know the term), but wasn't sure how to program it. I did see that each larger wheel would take more and more programming effort with diminishing return. I guessed that this was probably the best method, up to improvements by some small constant. (This was around 8th grade, forgive my naivete.)

4. Trial division: O(n^1.5/log n)
Wheel sieving is great, but wouldn't it be better to check divisibility by only primes? Not realizing the huge gap between N and sqrt(N), I originally thought this would be impractical. But trying it out I found this to be a further small improvement. But I paid for it in space, going from constant to O(sqrt(n)/log n).

5. Sieve of Eratosthenes: O(n log n)
What if you checked the whole list for primality at the same time, instead of going one-by-one? You could avoid doing divisions entirely, relying on the fact that if p|a, p|(a+p). You make a list as long as the number of primes you're going to check, marking all but the first as provisionally prime. For each prime p less than sqrt(N), mark 2p, 3p, ... as composite. When you're done, all remaining provisionally prime numbers are, in fact, prime. The memory use is large, though: since you hold a list as long as the interval itself, it takes O(n) memory. Suddenly, space is more of a limiting factor than time!

6. Segmented SoE: O(n log n)
By splitting the list into many small segments (perhaps as many as sqrt(N) segments with lengths as small as sqrt(N)) the memory use can be cut down to O(sqrt(n)). This is the first step back on the list, as it actually takes more time than the previous method. Although the asymptotic complexity is no worse, the big-O constant holds a lot of extra work determining where to start sieving on each piece.

7. Sieve of Atkin: O(n)
The sieve of Atkin is a much more difficult sieve to implement than the sieve of Eratosthenes. Instead of checking for the linear form n = a * b, it checks for various quadratic forms depending on the value of n mod 12. I had a working version of this sieve some time ago, though unfortunately I may have lost it. The careful programming necessary to make this form competitive is tricky; my version was really no better than the SoE for normal sizes.

Other fun sieves: Galway's dissected and hybrid sieves (the latter can be considered experimental) and the LPW-Sorenson pseudosquare sieve. These sieves are good for enumerating small numbers of large primes, perhaps all primes between 10^20 and 10^20 + 10^9. They cannot compete with the Sieve of Atkin on speed, though, only on space.

Note: Complexities reported here are (1) arithmetic complexity, not bit complexity, and (2) my calculations. They may not match other reported values, either because my algorithm is not the same or because the other uses bit complexity. The sieve of Atkin, for example, is usually described as sublinear -- O(n/log log n) -- because of a scaling wheel sieve built in and other such tricks. But a practical implementation does not vary the size of the wheel, so the true complexity is often linear. (Not that I should complain, it's quite fast regardless!)
CRGreathouse is offline  

  My Math Forum > College Math Forum > Number Theory

history, listing, personal, primes

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Personal Thoughts CherryPi Calculus 2 April 18th, 2012 04:19 AM
Listing members of this set help Flook Real Analysis 1 January 22nd, 2012 03:54 AM
Personal Characteristics and Lottery htamevolI Advanced Statistics 0 November 16th, 2010 12:35 PM
Signature too personal? The Chaz New Users 8 September 10th, 2010 04:38 AM
Trying to make history, or at least understand primes better approx Number Theory 6 February 24th, 2009 06:10 PM

Copyright © 2019 My Math Forum. All rights reserved.