J

#### jzakiya

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). See my paper for what/why is going on here.

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

*: 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

# 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

*)*

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 C/C++ gurus will do

good implementations. The methodology is very simple, since all I do

is additions, multiplications, and array reads/writes.

I would also like to the C implementations benchmarked against the

versions create by Daniel J Bernstein of the Sieve of Atkin (SoA). The

C code is here:

http://cr.yp.to/primesgen.html

Have fun with the code. ;-)

Jabari Zakiyareturn 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 C/C++ gurus will do

good implementations. The methodology is very simple, since all I do

is additions, multiplications, and array reads/writes.

I would also like to the C implementations benchmarked against the

versions create by Daniel J Bernstein of the Sieve of Atkin (SoA). The

C code is here:

http://cr.yp.to/primesgen.html

Have fun with the code. ;-)

Jabari Zakiya