Programming and general geekiness.

Sieving primes

When programming to calculate prime numbers you have a lot of options. The obvious (and slow) option is to make an array called primes and then loop up to a number, each time checking if the number in the loop (say x) can be divided by any of the primes that have already been calculated and if not add it to the array of primes. This method does work well, it is just very, very slow. I generated all the prime numbers up to 4,000,000 with a Java program running like this in just over an hour on a relatively slow computer. Using the sieve method on the same computer I was able to do it in ten seconds.

So how does sieving work? Say that you wanted to calculate all the prime numbers up to 10. You would mark 0-9 as True to state that they are prime. You would then take 2 and loop through all multiples of 2 marking them as false (not prime). This would then tell us that 4, 6 and 8 weren’t prime. We would then take 3 and mark all of its multiples as not prime (6 and 9). We could take four but we might as well check that it hasn’t been marked already so we can skip it. We don’t need to do five because clearly any multiples will be outside the array.

Here’s how we would do it in Python:

def primes(max):
	primes = [True] * max
	primes[1] = False
	for i in xrange(2, int(max/2)+1):
		if primes[i]:
			for x in xrange(2*i, max, i):
				primes[x] = False
	final = []
	for i in xrange(1, max):
		if primes[i]: final.append(i)
	return final

Let me go through that step by step:

  1. Create an array where all the numbers are marked as prime
  2. Set 1 as not prime
  3. Loop through all the values in the array – we only go half way because anything above max/2 will be greater than max
  4. We check that the algorithm currently thinks that it is prime
  5. We then loop through all multiples of that number marking them as not prime
  6. We create a new array
  7. We loop through the original array checking for primes and adding them to the new array
  8. Return the new array

Overall sieving primes is incredibly efficient if it is done properly and is far more effective than other techniques.

Advertisements

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

%d bloggers like this: