Ultimate Prime Sieve -- Sieve Of Zakiya (SoZ)

[jzakiya]

On Jun 13, 1:12 pm, jzakiya <jzak... at gmail.com> wrote:
> This is to announce the release of my paper "Ultimate Prime Sieve --
> Sieve of Zakiiya (SoZ)" in which I show and explain the development of
> a class of Number Theory Sieves to generate prime numbers.   I used
> Ruby 1.9.0-1 as my development environment on a P4 2.8 Ghz laptop.
>
> You can get the pdf of my paper and Ruby and Python source from here:
>
> http://www.4shared.com/dir/7467736/97bd7b71/sharing.html
>
> Below is a sample of one of the simple prime generators. I did a
> Python version of this in my paper (see Python source too).  The Ruby
> version below is the minimum array size version, while the Python has
> array of size N (I made no attempt to optimize its implementation,
> it's to show the method).
>
> class Integer
>    def primesP3a
>       # all prime candidates > 3 are of form  6*k+1 and 6*k+5
>       # initialize sieve array with only these candidate values
>       # where sieve contains the odd integers representatives
>       # convert integers to array indices/vals by  i = (n-3)>>1 =
> (n>>1)-1
>       n1, n2 = -1, 1;  lndx= (self-1) >>1;  sieve = []
>       while n2 < lndx
>          n1 +=3;   n2 += 3;   sieve[n1] = n1;  sieve[n2] = n2
>       end
>       #now initialize sieve array with (odd) primes < 6, resize array
>       sieve[0] =0;  sieve[1]=1;  sieve=sieve[0..lndx-1]
>
>       5.step(Math.sqrt(self).to_i, 2) do |i|
>          next unless sieve[(i>>1) - 1]
>          # p5= 5*i,  k = 6*i,  p7 = 7*i
>          # p1 = (5*i-3)>>1;  p2 = (7*i-3)>>1;  k = (6*i)>>1
>          i6 = 6*i;  p1 = (i6-i-3)>>1;  p2 = (i6+i-3)>>1;  k = i6>>1
>          while p1 < lndx
>              sieve[p1] = nil;  sieve[p2] = nil;  p1 += k;  p2 += k
>          end
>       end
>       return [2] if self < 3
>       [2]+([nil]+sieve).compact!.map {|i| (i<<1) +3 }
>    end
> end
>
> def primesP3(val):
>     # all prime candidates > 3 are of form  6*k+(1,5)
>     # initialize sieve array with only these candidate values
>     n1, n2 = 1, 5
>     sieve = [False]*(val+6)
>     while  n2 < val:
>         n1 += 6;   n2 += 6;  sieve[n1] = n1;   sieve[n2] = n2
>     # now load sieve with seed primes 3 < pi < 6, in this case just 5
>     sieve[5] = 5
>
>     for i in range( 5, int(ceil(sqrt(val))), 2) :
>        if not sieve[i]:  continue
>        #  p1= 5*i,  k = 6*i,  p2 = 7*i,
>        p1 = 5*i;  k = p1+i;  p2 = k+i
>        while p2 <= val:
>           sieve[p1] = False;  sieve[p2] = False;  p1 += k;  p2 += k
>        if p1 <= val:  sieve[p1] = False
>
>     primes = [2,3]
>     if val < 3 : return [2]
>     primes.extend( i for i in range(5, val+(val&1), 2)  if sieve[i] )
>
>     return primes
>
> Now to generate an array of the primes up to some N just do:
>
> Ruby:    10000001.primesP3a
> Python: primesP3a(10000001)
>
> The paper presents benchmarks with Ruby 1.9.0-1 (YARV).  I would love
> to see my various prime generators benchmarked with optimized
> implementations in other languages.  I'm hoping Python gurus will do
> better than I, though the methodology is very very simple, since all I
> do is additions, multiplications, and array reads/writes.
>
> Have fun with the code.  ;-)
>

CORRECTION:

http://cr.yp.to/primegen.html   NOT  "primesgen"

 Jabari Zakiya