Prime Sieve

Alex Egg,

Ever since I staring doing project Euler challengers, I’ve always been fascinated the “Greek Sieve” method of generating primes. I came across it while I was trying to find a faster way to generate primes and then read the wikipedia article on it.

Say I want to find all the primes up to 100. The algorithm is this:

  1. Generate a list of number from 0-100
  2. Starting at 2, increment the list by multiples of 2 (4, 6, 8… 100) and mark them.
  3. Continue, marking multiples of 3, 4, 5,…100 until complete
  4. The remainder of the list that isn’t marked is prime!

This is much faster than the more obvious brute-force method of iterating the list and doing a division test.

I originally implemented it in ruby, and I recently I re-implemnted it in c to do a speed test on my openwrt router:

class Prime
  def self.sieve(upto)
    a=[]
    (1..upto).each do |n|
      a.push true
    end

    (2..upto).each do |i|
      break if i>upto/2
      if(a[i])
        (2..upto).each do |j|
          k=j*i
          break if k>upto
          a[k]=false
        end
      end
    end
    primes=[]
    a.each_with_index do |tf, val|
      next if val <2
      if(tf) 
        primes.push val
      end
    end
    primes
  end 
end

I wrote this ruby implementation a long time ago. It’s kinda sloppy but it works. The first loop generates a list of true values. Then the second loop iterates the list and marks the multiples of 2,3,4,etc, by setting them false. It them pushes all trues to a new primes array. This looks like a O(n^2) implementation.

Here is the C impl. I wrote recently to run on my openwrt MIPS arch board:

#include <stdio.h>

int main( int argc, char *argv[])
{
	
	int i;
	int max=atoi( argv[1] );
	printf("generating primes up to %d\n",max);
	int nums[max]; 
	
	for(i=0; i<max; i++)
	{
		nums[i]=i;
		// printf("%d",i);
	}
	
	int p;
	int j;
	// O(n^2)  :(
	for(p=2; p<max; p++)
	{
		for(j=1; j*p<max; j++)
		{	
			if(nums[(j*p)] > p)
			{
				nums[(j*p)]=0;
			}
		}
	}
	
	
	//print result
	int k;
	for(k=0;k<max;k++)
	{
		if(nums[k]!=0)
			printf("%d\n", nums[k]);
	}

	return 0;
}

It’s the same idea as the ruby one – I wonder if it’s possible to get rid of the inner loop to get rid of the n^2 growth rate….


Permalink: prime-sieve

Tags:

Last edited by Alex Egg, 2016-10-05 19:15:21
View Revision History