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/9...1/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. ;-)
Jabari Zakiya
