# Prime Sieve

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:

- Generate a list of number from 0-100
- Starting at 2, increment the list by multiples of 2 (4, 6, 8… 100) and mark them.
- Continue, marking multiples of 3, 4, 5,…100 until complete
- 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:**